Dr. Matthias Mnich

orcid.jpg

Universität Bonn
Institute of Computer Science
Department of Theoretical Computer Science
Endenicher Allee 19a
D-53115 Bonn
Germany
mmnich---remove-this---@uni-bonn.de

Current Activities

Research Group

Current Students

  • Alexander Göke (PhD student at Bonn University), funded by DFG Project “Kernelization for Big Data” associated with DFG SPP 1736 "Algorithms for Big Data"
  • Simon Omlor (PhD student at Bonn University), funded by DFG Project “Multivariate Algorithms for High-Multiplicity Scheduling”
  • Roland Vincze (PhD student at Maastricht University), co-supervised with André Berger
  • Alisa Govzmann (MSc student at Bonn University)
  • Damir Ferizovi (MSc student at Karlsruhe Institute of Technology), co-supervised with Demian Hespe and Sebastian Lamm

Former Students

  • Stefano Ugliano (PhD student), funded by DFG Project “Big Data Kernelization” associated with DFG SPP 1736 "Algorithms for Big Data"
  • Simone Tummers (MSc, 2017)
  • René Wittmann (MSc, 2016)
  • Eva-Lotta Teutrine (MSc, 2016), awarded the Thesis Prize by the Bonner Informatik Gesellschaft e.V.
  • René Wittmann (BSc, 2014)
  • Alexandra Stern (BSc, 2014)
  • Lars Burghardt (BSc, 2014)
  • Christopher Brozek (BSc, 2014)
  • Antonia Eckhardt (BSc, 2014)
  • Robin Adner (BSc, 2014)
  • Oliver Déjon (MSc, 2013)

Research Interests

  • combinatorial optimization
  • scheduling
  • social choice theory
  • parameterized complexity
  • discrete mathematics

Current Teaching

Summer Term 2017

Winter Term 2016

Winter Term 2015/2016

Winter Term 2014/2015

  • Core Lecture “Pearls of Algorithms”, Graduate Course at Bonn University

Winter Term 2013/2014

Summer Term 2013

  • Core Lecture "Optimization", Undergraduate Course at Saarland University

Winter Term 2012/2013

Summer Term 2012

Selected Publications

  • Anna Adamaszek, Matthias Mnich, Katarzyna Paluch:
    New approximation algorithms for (1,2)-TSP
    ICALP 2018

List of Publications

Publications with Open Access logo are freely accessible through Open Access.

Preprints

  • André Berger, László Kozma, Matthias Mnich, Roland Vincze:
    Time- and space-optimal algorithms for the many-visits TSP
    Open Access preprint
  • Aida Abiad, Sander Gribling, Domenico Lahaye, Matthias Mnich, Guus Regts, Lluis Vena, Gerard Verweij, Peter Zwaneveld:
    On the complexity of solving a decision problem with flow-depending costs: the case of the IJsselmeer dikes
    Open Access preprint
  • Karthekeyan Chandrasekaran, Matthias Mnich, Sahand Mozaffari:
    Odd multiway cut in directed acyclic graphs
    Open Access preprint

2018+

  • Matthias Mnich, René van Bevern:
    Parameterized complexity of machine scheduling: 15 open problems
    Computers and Operations Research , to appear.
    Open Access preprint
  • Matthias Mnich, Heiko Röglin, Clemens Rösner:
    New deterministic algorithms for solving parity games
    Discrete Optimization , to appear.
    Open Access preprint
    original publication
  • Anna Adamaszek, Matthias Mnich, Katarzyna Paluch:
    New approximation algorithms for (1,2)-TSP
    Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP '18), Leibniz International Proceedings in Informatics 107, pp. 9:1–9:14.
    Open Access original publication
  • John Fearnley, Martin Gairing, Matthias Mnich, Rahul Savani:
    Reachability switching games
    Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP '18), Leibniz International Proceedings in Informatics 107, pp. 124:1–124:14.
    Open Access original publication
    Open Access preprint
  • Martin Koutecký, Dusan Knop, Matthias Mnich:
    A unifying framework for manipulation problems
    Proceedings of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS '18), pp. 256–264.
    original publication
    Open Access preprint
  • Matthias Mnich, Tobias Mömke:
    Improved integrality gap upper bounds for TSP with distances one and two
    European Journal of Operational Research 266(2), pp. 436-457.
    Open Access original publication
  • Matthias Mnich, Ignaz Rutter, Jens Schmidt:
    Linear-time recognition of map graphs with outerplanar witness
    Discrete Optimization 28, pp. 63-77.
    Open Access original publication
  • Matthias Mnich, Eva-Lotta Teutrine:
    Improved bounds for minimal feedback vertex sets in tournaments
    Journal of Graph Theory 88(3), pp. 482-506.
    Open Access original publication
  • Michael Etscheid, Matthias Mnich:
    Linear kernels and linear-time algorithms for finding large cuts
    Algorithmica 80(9), pp. 2574–2615.
    Open Access original publication
  • Krzysztof Fleszar, Matthias Mnich, Joachim Spoerhase:
    New algorithms for maximum disjoint paths based on tree-likeness
    Mathematical Programming 171(1–2), pp. 433–461.
    Open Access original publication
  • Matthias Mnich:
    Big Data algorithms beyond machine learning
    KI - Künstliche Intelligenz 32(1), pp. 9–17.
    Open Access original publication

2017

  • Matthias Mnich, Ildikó Schlotter:
    Stable marriage with covering constraints: A complete computational trichotomy
    Proceedings of the International Symposium on Algorithmic Game Theory (SAGT '17) , Lecture Notes in Computer Science 10504, pp. 320–332.
    original publication
    Open Access arXiv version
  • Martin Koutecký, Dusan Knop, Matthias Mnich:
    Combinatorial n-fold integer programming and applications
    Proceedings of the European Symposium on Algorithms (ESA '17), Leibniz International Proceedings in Informatics 87, pp. 54:1–54:14.
    Open Access original publication
  • Josh Alman, Matthias Mnich, Virginia Vassilevska Williams:
    Dynamic parameterized problems and algorithms
    Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP '17), Leibniz International Proceedings in Informatics 80, pp. 41:1–41:16.
    Open Access original publication
  • Matthias Mnich, Erik Jan van Leeuwen:
    Polynomial kernels for deletion to classes of acyclic digraphs
    Discrete Optimization 25, pp. 48-76.
    Open Access original publication
  • Martin Koutecky, Dusan Knop, Matthias Mnich:
    Voting and bribing in single exponential time
    Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS '17), Leibniz International Proceedings in Informatics 66, pp. 46:1–46:14.
    Open Access original publication
  • Zdenek Dvorak, Matthias Mnich:
    Large independent sets in triangle-free planar graphs
    SIAM Journal on Discrete Mathematics 31(2), pp. 1355-1373.
    original publication
    Open Access arXiv version
  • Michael Etscheid, Stefan Kratsch, Matthias Mnich, Heiko Röglin:
    Polynomial kernels for weighted problems
    Journal of Computer and System Sciences 84, pp. 1-10.
    original publication
    Open Access arXiv version

2016

  • Michael Etscheid, Matthias Mnich:
    Linear kernels and linear-time algorithms for finding large cuts
    Proceedings of the International Symposium on Algorithms and Computation (ISAAC '16), Leibniz International Proceedings in Informatics 64, pp. 31:1–31:13.
    Open Access original publication
  • Matthias Mnich, Eva-Lotta Teutrine:
    Improved bounds for minimal feedback vertex sets in tournaments
    Proceedings of the International Symposium on Parameterized and Exact Computation (IPEC '16), Leibniz International Proceedings in Informatics 63, pp. 24:1–24:10.
    Open Access original publication
  • Krzysztof Fleszar, Matthias Mnich, Joachim Spoerhase:
    New algorithms for maximum disjoint paths based on tree-likeness
    Proceedings of the European Symposium on Algorithms (ESA '16), Leibniz International Proceedings in Informatics 57, pp. 42:1–42:17.
    Open Access original publication
  • Matthias Mnich, Virginia Vassilevska Williams, László A. Végh:
    A 7/3-approximation for feedback vertex sets in tournaments
    Proceedings of the European Symposium on Algorithms (ESA '16), Leibniz International Proceedings in Informatics 57, pp. 67:1–67:14.
    Open Access original publication
  • Alina Ene, Matthias Mnich, Marcin Pilipczuk, Andrej Risteski:
    On routing disjoint paths in bounded treewidth graphs
    Proceedings of Scandinavian Symposium and Workshops on Algorithm Theory (SWAT '16), Leibniz International Proceedings in Informatics 53, pp. 15:1-15:15.
    Open Access original publication
  • Matthias Mnich, Ignaz Rutter, Jens M. Schmidt:
    Linear-time recognition of map graphs with outerplanar witness
    Proceedings of Scandinavian Symposium and Workshops on Algorithm Theory (SWAT '16), Leibniz International Proceedings in Informatics 53, pp. 5:1-5:14.
    Open Access original publication
  • Karl Bringmann, Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen:
    Parameterized complexity dichotomy for Steiner multicut
    Journal of Computer and System Sciences 82(6), pp. 1020-1043.
    original publication
    Open Access arXiv version
  • Anna Adamaszek, Michal Adamaszek , Matthias Mnich, Jens M. Schmidt:
    Lower bounds for locally highly connected graphs
    Graphs and Combinatorics 32(5), pp. 1641-1650.
    original publication
  • Matthias Mnich, Erik Jan van Leeuwen:
    Polynomial kernels for deletion to acyclic digraphs
    Proceedings of the International Symposium on Theoretical Aspects of Computer Science (STACS '16), Leibniz International Proceedings in Informatics 47, pp. 55:1-55:13.
    Open Access original publication
  • Matthias Mnich, Heiko Röglin, Clemens Rösner:
    New deterministic algorithms for solving parity games
    Proceedings of the Latin American Theoretical Informatics Symposium (LATIN '16), Lecture Notes in Computer Science 9644, pp. 634-645.
    original publication
  • Matthias Mnich:
    Large independent sets in subquartic planar graphs
    Proceedings of the International Workshop on Algorithms and Computation (WALCOM '16), Lecture Notes in Computer Science 9627, pp. 1-13.
    original publication

2015

  • Michael Etscheid, Stefan Kratsch, Matthias Mnich, Heiko Röglin:
    Polynomial kernels for weighted problems
    Proceedings of the International Symposium on Mathematical Foundations of Computer Science (MFCS '15), Lecture Notes in Computer Science 9235, pp. 287-298.
    original publication
    Open Access arXiv version
  • Matthias Mnich, Yash Raj Shrestha, Yongjie Yang:
    When Schwartz' conjecture holds
    Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI '15),
    Open Access original publication
  • Karl Bringmann, Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen:
    Parameterized complexity dichotomy for Steiner multicut
    Proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS '15), Leibniz International Proceedings in Informatics 30, pp. 157-170.
    Open Access original publication
  • Matthias Mnich, Andreas Wiese:
    Scheduling and fixed-parameter tractability
    Mathematical Programming Series B 154(1), pp. 533-562.
    original publication
    Open Access arXiv version
  • René van Bevern, Matthias Mnich, Rolf Niedermeier, Mathias Weller:
    Interval scheduling and colorful independent sets
    Journal of Scheduling 18(5), pp. 449-469.
    original publication
    Open Access arXiv version
  • Robert Crowston, Mark Jones, Matthias Mnich:
    Max-cut parameterized above the Edwards-Erdős bound
    Algorithmica 72(3), pp. 734-757.
    original publication
    Open Access arXiv version

2014

  • Zdeněk Dvořák, Matthias Mnich:
    Large independent sets in triangle-free planar graphs
    Proceedings of the European Symposium on Algorithms (ESA '14), Lecture Notes in Computer Science 8737, pp. 346-357.
    original publication
    Open Access arXiv version
  • Riko Jacob, Tobias Lieber, Matthias Mnich:
    Treewidth computation and kernelization in the parallel external memory model
    Proceedings of Theoretical Computer Science (TCS '14), Lecture Notes in Computer Science 8705, pp. 78-89.
    original publication
  • Henning Fernau, Fedor Fomin, Daniel Lokshtanov, Matthias Mnich, Geevarghese Philip, Saket Saurabh:
    Social choice meets graph drawing: How to get subexponential time algorithms for ranking and drawing problems
    Tsinghua Science and Technology 19(4), pp. 374-386.
    original publication
  • Matthias Mnich, Geevarghese Philip, Saket Saurabh, Ondřey Suchý:
    Beyond max-cut: λ-extendible properties parameterized above Poljak-Turzík bound
    Journal of Computer and System Sciences 80(7), pp. 1384-1403.
    original publication
    Open Access arXiv version
  • Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen:
    Parameterized complexity of induced graph matching on claw-free graphs
    Algorithmica 70(3), pp. 513-560.
    original publication
    Open Access arXiv version
  • Matthias Mnich, Andreas Wiese:
    Scheduling and fixed-parameter tractability
    Proceedings of the Conference on Integer Programming and Combinatorial Optimization (IPCO '14), Lecture Notes in Computer Science 8494, pp. 381-392.
    original publication
    Open Access arXiv version

2013

  • Sylvain Guillemot, Matthias Mnich:
    Kernel and fast algorithm for dense triplet inconsistency
    Theoretical Computer Science 494, pp. 134-143.
    original publication

2012

  • Ross Kang, Matthias Mnich, Tobias Müller:
    Induced matchings in subcubic planar graphs
    SIAM Journal on Discrete Mathematics 26(3), pp. 1383-1411.
    original publication
  • Matthias Mnich, Geevarghese Philip, Saket Saurabh, Ondřey Suchý:
    Beyond max-cut: λ-extendible properties parameterized above Poljak-Turzík bound
    Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS '12), Leibniz International Proceedings in Informatics 18, pp. 412–423.
    Open Access original publication
  • René van Bevern, Matthias Mnich, Rolf Niedermeier, Mathias Weller:
    Interval scheduling and colorful independent sets
    Proceedings of the International Symposium on Algorithms and Computation (ISAAC '12), Lecture Notes in Computer Science 7676, pp. 247-256.
    original publication
    Open Access arXiv version
  • Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen:
    Parameterized complexity of induced H-matching on claw-free graphs
    Proceedings of the European Symposium on Algorithms (ESA '12), Lecture Notes in Computer Science 7501, pp. 624-635.
    original publication
    Open Access arXiv version
  • Matthias Mnich, Rico Zenklusen:
    Bisections parameterized above tight lower bound
    Proceedings of the Workshop on Graph-Theoretic Concepts in Computer Science (WG '12), Lecture Notes in Computer Science 7551, pp. 184-193.
    original publication
  • Robert Crowston, Mark Jones, Matthias Mnich:
    Max-cut parameterized above the Edwards-Erdős-bound
    Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP '12), Lecture Notes in Computer Science 7391, pp. 242-253.
    original publication
    Open Access arXiv version
  • Gregory Gutin, Leo van Iersel, Matthias Mnich, Anders Yeo:
    Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
    Journal of Computer and System Sciences 78(1), pp. 151-163.
    original publication
    Open Access arXiv version

2011

  • Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen, Gerhard J. Woeginger:
    Domination when the stars are out
    Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP '11), Lecture Notes in Computer Science 6755, pp. 462-473.
    original publication
    Open Access arXiv version
  • Daniel Lokshtanov, Matthias Mnich, Saket Saurabh:
    Planar k-path in subexponential time and polynomial space
    Proceedings of the Workshop on Graph-Theoretic Concepts in Computer Science (WG '11), Lecture Notes in Computer Science 6986, pp. 262-270.
    original publication
  • Matthias Mnich:
    Allemaal op een rijtje (Philips Prize Lecture 2010)
    Nieuw Archief voor Wiskunde 5(12), pp. 25-28.
    Open Access original publication
  • Matthias Mnich:
    Book Review Exact Exponential Algorithms
    Operations Research Letters 39(3), pp. 229-230.
    original publication
  • Daniel Lokshtanov, Matthias Mnich, Saket Saurah:
    Linear kernel for planar connected dominating set
    Theoretical Computer Science 412(23), pp. 2536-2543
    original publication

2010

  • Matthias Mnich:
    Algorithms in Moderately Exponential Time
    PhD thesis, Eindhoven University of Technology, Eindhoven, The Netherlands, 216 p.
    Open Access original publication
  • Gregory Gutin, Leo van Iersel, Matthias Mnich, Anders Yeo:
    All ternary permutation constraint satisfaction problems parameterized above average have polynomial kernels
    Proceedings of the 18th European Symposium on Algorithms (ESA '10), Lecture Notes in Computer Science 6346, pp. 326-337.
    original publication
    Open Access arXiv version
  • Serge Gaspers, Matthias Mnich:
    Feedback vertex sets in tournaments
    Proceedings of the 18th European Symposium on Algorithms (ESA '10), Lecture Notes in Computer Science 6346, pp. 267-277.
    original publication
    Open Access arXiv version
  • Ross Kang, Matthias Mnich, Tobias Müller:
    Induced matchings in subcubic planar graphs
    Proceedings of the 18th European Symposium on Algorithms (ESA '10), Lecture Notes in Computer Science 6347, pp. 112-122.
    original publication
  • Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov, Matthias Mnich, Geevarghese Philip, Saket Saurabh:
    Ranking and drawing in subexponential time
    Proceedings of the 21st International Workshop on Combinatorial Algorithms (IWOCA '10), Lecture Notes in Computer Science 6460, pp. 337-348.
    original publication
  • Sylvain Guillemot, Matthias Mnich:
    Kernel and fast algorithm for dense triplet inconsistency
    Proceedings of 7th Annual Conference Theory and Applications of Models of Computation (TAMC '10), Lecture Notes in Computer Sciene 6108, pp. 247-257.
    original publication
  • Gregory Gutin, Eun Jung Kim, Matthias Mnich, Anders Yeo:
    Betweenness parameterized above tight lower bound
    Journal of Computer and System Sciences 76(8), pp. 872-878.
    original publication
    Open Access arXiv version

2009

  • Leo van Iersel, Steven Kelk, Matthias Mnich:
    Uniqueness, intractability and exact algorithms: Reflections on level-k phylogenetic networks
    Journal of Bioinformatics and Computational Biology 7(4), pp. 597-623.
    original publication
  • Michael Fellows, Daniel Lokshtanov, Neeldhara Misra, Matthias Mnich, Frances Rosamond, Saket Saurabh:
    The complexity ecology of parameters: An illustration using bounded max leaf number
    Theory of Computing Systems 45(4), pp. 822-848.
    original publication
  • Daniel Lokshtanov, Matthias Mnich, Saket Saurabh:
    Linear kernel for planar connected dominating set
    Proceedings of 6th Annual Conference Theory and Applications of Models of Computation (TAMC '09), Lecture Notes in Computer Science 5532, pp. 281-290.
    original publication

2006

  • Matthias Mnich:
    Correlated Equilibria in Succinctly Representable Games.
    MSc thesis, The London School of Economics and Political Science, London, United Kingdom, August 2006.

Page Tools