Saarland University
Department of Computer Science
Computational Complexity
Computational Complexity

Publications

Teaching

Workshops

Tobias Mömke

Address:
Universität des Saarlandes
Tobias Mömke
Campus Geb E13
Postfach 42 (Bläser)
66123 Saarbrücken
Germany

Office: Building E1 3, Room 422
Phone: +49 681 302-5502
Email: "moemke" at "cs.uni-saarland.de"

My research aims to develop new algorithmic approaches for computationally hard problems. In particular I am interested in algorithms for global NP-hard optimization problems such as the traveling salesperson problem or the Steiner tree problem. I am particularly interested in using and developing techniques from combinatorial optimization, with a special focus on linear programming and related advanced methods.

As a second major theme of my research, I focus on online problems. The purpose of online computation is to analyze strategies to take decisions in the absence of future information. Unlike in the case of NP-hard optimization problems, the hardness of online problems does not arise from limited time resources but instead from a limited knowledge of future events. My research on online algorithms aims to identify the inherent properties of online problems that are responsible for the existence or nonexistence of useful algorithms.

Grants

DFG Project "Neuartige Approximationstechniken für Traveling Salesperson Probleme"

Program Committee Member

19th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2016)

Courses

2014: "Selected Topics in Combinatorial Optimization" at Saarland University.

2012: FDD3402 Combinatorial Optimization at KTH - Royal Institute of Technology, Stockholm, Sweden.

Publications

    Journal Articles

  1. Tobias Mömke and Ols Svensson. Removing and adding edges for the traveling salesman problem. Journal of the ACM. 63 2:1–2:28, 2016.
  2. Tobias Mömke. An improved approximation algorithm for the traveling salesman problem with relaxed triangle inequality. Information Processing Letters. 115:866–871, 2015.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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.
  10. Conference Proceedings

  11. 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  of the 18th Conference on Integer Programming and Combinatorial Optimization (IPCO 2016), 2016. To appear.
  12. 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.
  13. 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.
  14. 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.
  15. 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.
  16. 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.
  17. 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.
  18. 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)
  19. 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.
  20. 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.
  21. 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.
  22. 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.
  23. 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.
  24. 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.
  25. 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.
  26. 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.
  27. 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.
  28. 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.
  29. 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.
  30. 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.
  31. 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.
  32. 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.
  33. 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.
  34. Selected Technical Reports

  35. Matthias Mnich and Tobias Mömke. Improved integrality gap upper bounds for TSP with distances one and two. CoRR, abs/1312.2502, 2013.
  36. Tobias Mömke. A Competitive Ratio Approximation Scheme for the k-Server Problem in Fixed Finite Metrics. CoRR, abs/1303.2963, (2013).
  37. Dennis Komm, Rasitislav Královič, Richard Královič, and Tobias Mömke. Randomized online computation with high probability guarantees. CoRR, abs/1302.2805, 2013.
  38. Hans-Joachim Böckenhauer, Dennis Komm, Rastislav Královič, Richard Královič, and Tobias Mömke. Online algorithms with advice. Technical Report 614, ETH Zürich, 2009. PDF.
  39. Theses

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

Last updated: 2016-01-31