Prof. Dr. Tobias Mömke

Tobias

Universität Bremen
FB3: Mathematik/Informatik
Bibliothekstr. 5.
28359 Bremen
Germany

Office: MZH 3210
Phone: +49 (421) 218-63610
Email

Office hours: by appointment

Refereed Journal Publications

  • Matthias Mnich and Tobias Mömke. Improved integrality gap upper bounds for TSP with distances one and two. European Journal of Operational Research. 266(2):436–457, 2018. CoRR, abs/1312.2502.
  • Adam Kurpisz, Monaldo Mastrolilli, Claire Mathieu, Tobias Mömke, Víctor Verdugo, and Andreas Wiese. Semidefinite and linear programming integrality gaps for scheduling identical machines. Mathematical Programming. 2017.
  • Holger Dell, Eun Jung Kim, Michael Lampis, Valia Mitsou, and Tobias Mömke. Complexity and Approximability of Parameterized MAX-CSPs. Algorithmica. 2017. CoRR, abs/1511.05546.
  • Hans-Joachim Böckenhauer, Dennis Komm, Rastislav Královič, Richard Královič, and Tobias Mömke. Online Algorithms with Advice: the Tape Model. Information and Computation. 254(1):59–83, 2017.
  • Tobias Mömke and Ola Svensson. Removing and adding edges for the traveling salesman problem. Journal of the ACM. 63 2:1–2:28, 2016. CoRR, abs/1104.3090.
  • Tobias Mömke. An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality. Information Processing Letters. 115:866–871, 2015. CoRR, abs/1412.6755.
  • Hans-Joachim Böckenhauer, Tobias Mömke, and Monika Steinová. Improved approximations for TSP with simple precedence constraints. Journal of Discrete Algorithms. 21:32–40, 2013.
  • Christos A. Kapoutsis, Richard Královič, and Tobias Mömke. Size complexity of rotating and sweeping automata. Journal of Computer and System Sciences, 78(2):537–558, March 2012. (c) Elsevier, doi:10.1016/j.jcss.2011.06.004.
  • Hans-Joachim Böckenhauer, Karin Freiermuth, Juraj Hromkovič, Tobias Mömke, Andreas Sprock, and Björn Steffen. The Steiner tree reoptimization problem in graphs with sharpened triangle inequality. Journal of Discrete Algorithms, 11:73–86, 2012.
  • Davide Bilò, Hans-Joachim Böckenhauer, Dennis Komm, Richard Královič, Tobias Mömke, Sebastian Seibert, and Anna Zych. Reoptimization of the shortest common superstring problem. Algorithmica, 61(2):227–251, 2011. (c) Springer-Verlag, SpringerLink.
  • Hans-Joachim Böckenhauer, Juraj Hromkovič, Richard Královič, Tobias Mömke, and Peter Rossmanith. Reoptimization of Steiner trees: Changing the terminal set. Theoretical Computer Science, 410(36):3428–3435, 2009. (c) Elsevier B.V., doi:10.1016/j.tcs.2008.04.039.
  • Tobias Mömke. On the power of randomization for job shop scheduling with k-units length tasks. RAIRO Theoretical Informatics and Applications, 43:189–207, 2009. (c) EDP Sciences, doi: 10.1051/ita:2008024.
  • Juraj Hromkovič, Tobias Mömke, Kathleen Steinhöfel, and Peter Widmayer. Job shop scheduling with unit length tasks: bounds and algorithms. Algorithmic Operations Research, 2(1):1–14, 2007.

Refereed Conference Publications

  • Shilpa Garg and Tobias Mömke. A QPTAS for Gapless MEC. In Proc. of the 26th Annual European Symposium on Algorithms (ESA 2018), to appear, 2018. CoRR, abs/1804.10930.
  • Fabrizio Grandoni, Tobias Mömke, Andreas Wiese, and Hang Zhou. A (5/3 + epsilon)-Approximation for Unsplittable Flow on a Path: Placing Small Tasks into Boxes. In Proc. of the 50th Annual ACM Symposium on Theory of Computation (STOC 2018), pages 607–619, 2018.
  • Anna Adamaszek, Antonios Antoniadis, Amit Kumar and Tobias Mömke. Approximating Airports and Railways. In Proc. of the 35th International Symposium on Theoretical Aspects of Computer Science (STACS 2018), pages 5:1–5:13, 2018.
  • László Kozma and Tobias Mömke. Maximum Scatter TSP in Doubling Metrics. In Proc. of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), pages 143–153, 2017. CoRR, abs/1512.02963.
  • Fabrizio Grandoni, Tobias Mömke, Andreas Wiese, and Hang Zhou. To Augment or Not to Augment: Solving Unsplittable Flow on a Path by Creating Slack. In Proc. of the 28th ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), pages 2411–2422, 2017.
  • Adam Kurpisz, Monaldo Mastrolilli , Claire Mathieu, Tobias Mömke, Victor Verdugo, and Andreas Wiese. Semidefinite and linear programming integrality gaps for scheduling identical machines. In Proc. of the 18th Conference on Integer Programming and Combinatorial Optimization (IPCO 2016), pages 152–163, 2016.
  • Anna Adamaszek, Antonios Antoniadis, and Tobias Mömke. Airports and Railways: Facility Location Meets Network Design . In Proc. of the 33rd International Symposium on Theoretical Aspects of Computer Science (STACS 2016), pages 6:1–6:14, 2016.
  • Stefan Dobrev, Juraj Hromkovič, Dennis Komm, Richard Královič, Rastislav Královič, and Tobias Mömke. The Complexity of Paging under a Probabilistic Adversary. In Proc. of the 42nd International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2016), pages 265–276, 2016.
  • Keshav Goyal and Tobias Möomke. Robost reoptimization of Steiner trees. Proc.  of the 35th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2015), pages 10–24, 2015.
  • Holger Dell, Eunjung Kim, Michael Lampis, Valia Mitsou, and Tobias Mömke. Complexity and approximability for parameterized CSPs. In Proc. of the 10th International Symposium on Parameterized and Exact Computation (IPEC 2015), pages 294–306, 2015.
  • Tobias Mömke and Andreas Wiese. A (2+epsilon)-Approximation Algorithm for the Storage Allocation Problem. In Proc. of the 42nd International Colloquium on Automata, Languages, and Programming (ICALP 2015), pages 973–984, 2015.
  • Jatin Batra, Naveen Garg, Amit Kumar, Tobias Mömke, and Andreas Wiese. New Approximation Schemes for Unsplittable Flow on a Path. In Proc. of the 26th ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), pages 47–58, 2015.
  • Dennis Komm, Rastislav Královič, Richard Královič, and Tobias Mömke. Randomized online algorithms with high probability guarantees. In Proc. of the 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), pages 470-481, 2014. Leibniz International Proceedings in Informatics (LIPIcs) (pdf)
  • Dennis Komm, Richard Královič, and Tobias Mömke. On the advice complexity of the set cover problem. In Proc. of the 7st Interational Computer Science Symposium in Russia (CSR 2012), pages 241–252, 2012. (c) Springer-Verlag, SpringerLink.
  • Tobias Mömke and Ola Svensson. Approximating graphic TSP by matchings. In Proc. of the 52nd Annual Symposium on Foundations of Computer Science (FOCS 2011), Best Paper Award, pages 560–569, October 2011.
  • Tobias Mömke. Structural properties of hard metric TSP inputs. In Proc. of the 37th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2011), volume 6543 of Lecture Notes in Computer Science, pages 394–405, January 2011. (c) Springer-Verlag, SpringerLink.
  • Hans-Joachim Böckenhauer, Juraj Hromkovic, and Tobias Mömke. Improved approximations for hard optimization problems via problem instance classification. In Rainbow of Computer Science, pages 3–19, 2011.
  • Hans-Joachim Böckenhauer, Karin Freiermuth, Juraj Hromkovič, Tobias Mömke, Andreas Sprock, and Björn Steffen. The Steiner tree reoptimization problem with sharpened triangle inequality. In Proc. of the 7th International Conference on Algorithms and Complexity (CIAC 2010), volume 6078 of Lecture Notes in Computer Science, pages 180–191, February 2010. (c) Springer-Verlag, SpringerLink.
  • Hans-Joachim Böckenhauer, Ralf Klasing, Tobias Mömke, and Monika Steinová. Improved approximations for TSP with simple precedence constraints. In Proc. of the 7th International Conference on Algorithms and Complexity (CIAC 2010), volume 6078 of Lecture Notes in Computer Science, pages 61–72, 2010. (c) Springer-Verlag, SpringerLink.
  • Davide Bilò, Hans-Joachim Böckenhauer, Dennis Komm, Richard Královič, Tobias Mömke, Sebastian Seibert, and Anna Zych. Reoptimization of the shortest common superstring problem. In Proc. of the 20th Annual Symposium on Combinatorial Pattern Matching (CPM 2009), volume 5577 of Lecture Notes in Computer Science, pages 78–91, 2009. (c) Springer-Verlag, SpringerLink.
  • Hans-Joachim Böckenhauer, Dennis Komm, Rastislav Královič, Richard Královič, and Tobias Mömke. On the advice complexity of online problems. In Proc. of the 20th International Symposium on Algorithms and Computation (ISAAC 2009), volume 5878 of Lecture Notes in Computer Science, pages 331–340, 2009. (c) Springer-Verlag, SpringerLink.
  • Davide Bilò, Hans-Joachim Böckenhauer, Juraj Hromkovič, Richard Královič, Tobias Mömke, Peter Widmayer, and Anna Zych. Reoptimization of Steiner trees. In Proc. of the 11th Scandinavian Workshop on Algorithm Theory (SWAT 2008), volume 5124 of Lecture Notes in Computer Science, pages 258–269, 2008. (c) Springer-Verlag, SpringerLink.
  • Hans-Joachim Böckenhauer, Juraj Hromkovič, Tobias Mömke, and Peter Widmayer. On the hardness of reoptimization. In Proc. of the 34th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2008), volume 4910 of Lecture Notes in Computer Science, pages 50–65, Berlin, 2008. (c) Springer-Verlag, SpringerLink.
  • Christos A. Kapoutsis, Richard Královič, and Tobias Mömke. On the size complexity of rotating and sweeping automata. In Proc. of the 12th Interational Conference on Developments in Language Theory (DLT 2008), volume 5257 of Lecture Notes in Computer Science, pages 455–466, 2008. (c) Springer-Verlag, SpringerLink.
  • Hans-Joachim Böckenhauer, Juraj Hromkovič, Richard Královič, Tobias Mömke, and Kathleen Steinhöfel. Efficient algorithms for the spoonerism problem. In Proc. of the 4th International Conference on FUN with Algorithms (FUN 2007), volume 4475 of Lecture Notes in Computer Science, pages 78–92, Berlin, 2007. (c) Springer-Verlag, SpringerLink.
  • Christos A. Kapoutsis, Richard Královič, and Tobias Mömke. An exponential gap between LasVegas and deterministic sweeping finite automata. In Proc. of the 4th International Symposium on Stochastic Algorithms: Foundations and Applications (SAGA 2007), volume 4665 of Lecture Notes in Computer Science, pages 130–141, 2007. (c) Springer-Verlag, SpringerLink.
  • Richard Královič and Tobias Mömke. Approximation hardness of the traveling salesman reoptimization problem. In Proc. of the 3rd Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2007), pages 97–104, 2007.
  • Tobias Mömke. On the power of randomization for job shop scheduling with k-units length tasks. In Proc. of the 2nd Doctoral Workshop on Mathematical and Engineering Methods in Computer Science (MEMICS 2006), pages 121–128, 2006.

Selected Technical Reports

  • Tobias Mömke. A Competitive Ratio Approximation Scheme for the k-Server Problem in Fixed Finite Metrics. CoRR, abs/1303.2963, 2013.

Theses

  • Tobias Mömke. Algorithmic approaches for solving hard problems: approximation and complexity. Doctoral dissertation, ETH Zurich, 2009.
  • Tobias Mömke. Online job shop scheduling with k-units length tasks. Diploma thesis, RWTH Aachen University, 2006.

Valid XHTML 1.0 Transitional