2025

• A quasi-polynomial time algorithm for multi-arrival on tree-like multigraphs
  Ghorbani, Ebrahim; Hoff, Jonah Leander; Mnich, Matthias
  International Symposium on Theoretical Aspects of Computer Science (STACS 2025)
  Open Access | Publisher DOI
• Approximate minimum tree cover in all symmetric monotone norms simultaneously
  Kaul, Matthias; Luo, Kelin; Mnich, Matthias; Röglin, Heiko
  International Symposium on Theoretical Aspects of Computer Science (STACS 2025)
  Open Access | Publisher DOI
• Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
  Bergougnoux, Benjamin; Chekan, Vera; Kanté, Mamadou Moustapha; Mnich, Matthias; Oum, Sang-il; Pilipczuk, Michał; Leeuwen, Erik Jan van
  ACM Transactions on Computation Theory (2025)
  Open Access

2024

• Serial batching to minimize the weighted number of tardy jobs
  Hermelin, Danny; Mnich, Matthias; Omlor, Simon
  Journal of Scheduling (2024)
  Open Access | Publisher DOI
• Single-Machine Scheduling to Minimize the Number of Tardy Jobs with Release Dates
  Kaul, Matthias; Mnich, Matthias; Molter, Hendrik
  International Symposium on Parameterized and Exact Computation (IPEC 2024)
  Open Access | Publisher DOI
• A (3/2 + 1/e)-Approximation algorithm for ordered TSP
  Armbruster, Susanne; Mnich, Matthias; Nägele, Martin
  International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2024)
  Open Access | Publisher DOI
• No polynomial kernels for knapsack
  Heeger, Klaus; Hermelin, Danny; Mnich, Matthias; Shabtay, Dvir
  International Colloquium on Automata, Languages and Programming (ICALP 2024)
  Open Access | Publisher DOI
• New support bounds and proximity bounds for integer linear programming
  Berndt, Sebastian; Mnich, Matthias; Stamm, Tobias
  International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2024)
  Publisher DOI
• Approximating sparsest cut in low-treewidth graphs via combinatorial diameter
  Chalermsook, Parinya; Kaul, Matthias; Mnich, Matthias; Spoerhase, Joachim; Uniyal, Sumedha; Vaz, Daniel
  ACM Transactions in Algorithms (2024)
  Publisher DOI
• Efficient Cost-Minimization Schemes for Electrical Energy Demand Satisfaction by Prosumers in Microgrids with Battery Storage Capabilities
  Codazzi, Laura; Csáji, Gergely; Mnich, Matthias
  International Joint Conference on Artificial Intelligence (IJCAI 2024)
  Open Access | Publisher DOI

2023

• Improved Approximations for Vector Bin Packing via Iterative Randomized Rounding
  Kulik, Ariel; Mnich, Matthias; Shachnai, Hadas
  IEEE Annual Symposium on Foundations of Computer Science (FOCS 2023)
  Publisher DOI
• A (3/2 + ε)-Approximation for multiple TSP with a variable number of depots
  Deppert, Max; Kaul, Matthias; Mnich, Matthias
  European Symposium on Algorithms (ESA 2023)
  Open Access | Publisher DOI
• High multiplicity N-fold IP via configuration LP
  Knop, Dušan; Koutecký, Martin; Levin, Asaf; Mnich, Matthias; Onn, Shmuel
  Mathematical Programming (2023)
  Open Access | Publisher DOI
• Approximations for many-visits multiple traveling salesman problems
  Bérczi, Kristóf; Mnich, Matthias; Vincze, Roland
  Omega 116: 102816 (2023)
  Open Access | Publisher DOI
• Recent advances in practical data reduction
  Abu-Khzam, Faisal N.; Lamm, Sebastian; Mnich, Matthias; Noe, Alexander; Schulz, Christian; Strash, Darren
  Lecture notes in computer science (2022)
  Open Access | Publisher DOI
• Checkpoint placement for systematic fault-injection campaigns
  Dietrich, Christian; Thomas, Tim-Marek; Mnich, Matthias
  IEEE/ACM International Conference on Computer-Aided Design (ICCAD 2023)
  Open Access | Publisher DOI
• New support size bounds for integer programming, applied to makespan minimization on uniformly related machines
  Berndt, Sebastian; Brinkop, Hauke; Jansen, Klaus; Mnich, Matthias; Stamm, Tobias
  International Symposium on Algorithms and Computation (ISAAC 2023)
  Open Access | Publisher DOI
• Space-efficient parameterized algorithms on graphs of low shrubdepth
  Bergougnoux, Benjamin; Chekan, Vera; Ganian, Robert; Kanté, Mamadou Moustapha; Mnich, Matthias; Oum, Sang-il; Pilipczuk, Michał; Leeuwen, Erik Jan van
  European Symposium on Algorithms (ESA 2023)
  Open Access | Publisher DOI

2022

• Parameterized algorithms for generalizations of directed feedback vertex set  
  Göke, Alexander; Marx, Dániel; Mnich, Matthias
  Discrete Optimization (2022)
  Open Access | Publisher DOI
• An asymptotic (4/3+epsilon)-approximation for the 2-dimensional vector bin packing problem
  Kulik, Ariel; Mnich, Matthias; Shachnai, Hadas
  arXiv: 2205.12828 (2022)
  Open Access | Publisher DOI
• Exponentially faster fixed-parameter algorithms for high-multiplicity scheduling
  Fischer, David; Golak, Julian; Mnich, Matthias
  arXiv: 2203.03600 (2022)
  Open Access | Publisher DOI
• A 3/2-approximation for the metric many-visits path TSP
  Bérczi, Kristóf; Mnich, Matthias; Vincze, Roland
  SIAM Journal on Discrete Mathematics (2022)
  Open Access | Publisher DOI
• A survey on graph problems parameterized above and below guaranteed values
  Gutin, Gregory Z.; Mnich, Matthias
  arXiv: 2207.12278 (2022)
  Open Access | Publisher DOI
• Hitting weighted even cycles in planar graphs
  Göke, Alexander; Koenemann, Jochen; Mnich, Matthias; Sun, Hao
  SIAM Journal on Discrete Mathematics (2022)
  Open Access | Publisher DOI

2021

• Parameterized complexity of configuration integer programs
  Knop, Dušan; Koutecký, Martin; Levin, Asaf; Mnich, Matthias; Onn, Shmuel
  Operations Research Letters (2021)
  Open Access | Publisher DOI
• Hitting weighted even cycles in planar graphs
  Göke, Alexander; Koenemann, Jochen; Mnich, Matthias; Sun, Hao
  International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2021)
  Open Access | Publisher DOI
• Reachability switching games
  Fearnley, John; Gairing, Martin; Mnich, Matthias; Savani, Rahul
  Logical Methods in Computer Science (2021)
  Open Access | Publisher DOI
• Approximating sparsest cut in low-treewidth graphs via combinatorial diameter
  Chalermsook, Parinya; Kaul, Matthias; Mnich, Matthias; Spoerhase, Joachim; Uniyal, Sumedha; Vaz, Daniel
  arXiv: 2111.06299 (2021)
  Open Access
• Efficient approximations for many-visits multiple traveling salesman problems
  Bérczi, Kristóf; Mnich, Matthias; Vincze, Roland
  arXiv: 2201.02054 (2021)
  Open Access

2020

• Combinatorial n-fold integer programming and applications
  Knop, Dušan; Koutecký, Martin; Mnich, Matthias
  Mathematical Programming (2020)
  Open Access | Publisher DOI
• On the complexity of solving a decision problem with flow-depending costs: The case of the IJsselmeer dikes
  Abiad, Aida; Gribling, Sander; Lahaye, Domenico; Mnich, Matthias; Regts, Guus; Vena, Luis; Verweij, Gerard; Zwaneveld, Peter
  Discrete Optimization (2020)
  Publisher DOI
• Voting and bribing in single-exponential time
  Knop, Dušan; Koutecký, Martin; Mnich, Matthias
  ACM Transactions on Economics and Computation 8 (3): 12 (2020)
  Open Access | Publisher DOI
• Stable matchings with covering constraints: a complete computational trichotomy
  Mnich, Matthias; Schlotter, Ildikó
  Algorithmica (2020)
  Open Access | Publisher DOI
• Dense Steiner problems: approximation algorithms and inapproximability
  Karpinski, Marek; Lewandowski, Mateusz; Meesum, Syed Mohammad; Mnich, Matthias
  arXiv: 2004.14102 (2020)
  
• Dynamic parameterized problems and algorithms
  Alman, Josh; Mnich, Matthias; Vassilevska Williams, Virginia
  ACM Transactions on Algorithms (2020)
  Publisher DOI
• Engineering kernelization for maximum cut
  Ferizovic, Damir; Hespe, Demian; Lamm, Sebastian; Mnich, Matthias; Schulz, Christian; Strash, Darren
  Symposium on Algorithm Engineering and Experiments (ALENEX 2020)
  Publisher DOI
• Hitting long directed cycles is fixed-parameter tractable
  Göke, Alexander; Marx, Dániel; Mnich, Matthias
  International Colloquium on Automata, Languages, and Programming (ICALP 2020)
  Open Access | Publisher DOI
• Odd multiway cut in directed acyclic graphs
  Chandrasekaran, Karthekeyan; Mnich, Matthias; Mozaffari, Sahand
  SIAM Journal on Discrete Mathematics (2020)
  Publisher DOI
• Recent advances in practical data reduction
  Abu-Khzam, Faisal; Lamm, Sebastian; Mnich, Matthias; Noe, Alexander; Schulz, Christian; Strash, Darren
  arXiv: 2012.12594 (2020)
  Open Access
• Solving packing problems with few small items using rainbow matchings
  Bannach, Max; Berndt, Sebastian; Maack, Marten; Mnich, Matthias; Lassota, Alexandra; Rau, Malin; Skambath, Malte
  International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)
  Open Access | Publisher DOI
• Time- and space-optimal algorithm for the many-visits TSP
  Berger, André; Kozma, László; Mnich, Matthias; Vincze, Roland
  ACM Transactions on Algorithms (2020)
  Publisher DOI

2019

• Resolving infeasibility of linear systems: a parameterized approach
  Göke, Alexander; Mendoza Cadena, Lydia Mirabel; Mnich, Matthias
  International Symposium on Parameterized and Exact Computation (IPEC 2019)
  Open Access | Publisher DOI
• Multitype integer monoid optimization and applications
  Knop, Dušan; Koutecký, Martin; Levin, Asaf; Mnich, Matthias; Onn, Shmuel
  arXiv: 1909.07326 (2019)
  Open Access
• A time- and space-optimal algorithm for the many-visits TSP
  Berger, André; Kozma, László; Mnich, Matthias; Vincze, Roland
  ACM-SIAM Symposium on Discrete Algorithms (SODA 2019)
  Open Access | Publisher DOI
• Degree-bounded generalized polymatroids and approximating the metric many-visits TSP
  Bérczi, Kristóf; Berger, André; Mnich, Matthias; Vincze, Roland
  arxiv:1911.09890 (2019)
  Open Access
• Domination when the stars are out
  Hermelin, Danny; Mnich, Matthias; Leeuwen, Erik Jan van; Woeginger, Gerhard
  ACM Transactions on Algorithms (2019)
  Publisher DOI
• Parameterized Algorithms for generalizations of directed feedback vertex set
  Göke, Alexander; Marx, Dániel; Mnich, Matthias
  11th International Conference on Algorithms and Complexity (CIAC 2019)
  Publisher DOI

2018

• Parameterized complexity of machine scheduling: 15 open problems
  Mnich, Matthias; van Bevern, René
  Computers (2018)
  Publisher DOI
• New deterministic algorithms for solving parity games
  Mnich, Matthias; Röglin, Heiko; Rösner, Clemens
  Discrete Optimization (2018)
  Publisher DOI
• Linear-time recognition of map graphs with outerplanar witness
  Mnich, Matthias; Rutter, Ignaz; Schmidt, Jens M.
  Discrete Optimization (2018)
  Publisher DOI
• A unifying framework for manipulation problems
  Knop, Dušan; Koutecký, Martin; Mnich, Matthias
  17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2018)
  
• Improved integrality gap upper bounds for TSP with distances one and two
  Mnich, Matthias; Mömke, Tobias
  European Journal of Operational Research (2018)
  Publisher DOI
• New algorithms for maximum disjoint paths based on tree-likeness
  Fleszar, Krzysztof; Mnich, Matthias; Spoerhase, Joachim
  Mathematical Programming (2018)
  Publisher DOI
• New approximation algorithms for (1,2)-TSP
  Adamaszek, Anna; Mnich, Matthias; Paluch, Katarzyna
  45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
  Publisher DOI

2017

• Improved bounds for minimal feedback vertex sets in tournaments
  Mnich, Matthias; Teutrine, Eva Lotta
  Journal of Graph Theory (2018)
  Open Access | Publisher DOI
• Linear kernels and linear-time algorithms for finding large cuts
  Etscheid, Michael; Mnich, Matthias
  Algorithmica (2018)
  Open Access | Publisher DOI
• Big data algorithms beyond machine learning
  Mnich, Matthias
  Künstliche Intelligenz 32 (1): 9-17 (2018)
  Open Access | Publisher DOI
• Combinatorial n-fold integer programming and applications
  Knop, Dušan; Koutecký, Martin; Mnich, Matthias
  25th European Symposium on Algorithms (ESA 2017)
  Open Access | Publisher DOI
• Dynamic parameterized problems and algorithms
  Alman, Josh; Mnich, Matthias; Vassilevska Williams, Virginia
  44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
  Publisher DOI
• Polynomial kernels for deletion to classes of acyclic digraphs
  Mnich, Matthias; Leeuwen, Erik Jan van
  Discrete Optimization (2017)
  Publisher DOI
• Voting and bribing in single-exponential time
  Knop, Dušan; Koutecký, Martin; Mnich, Matthias
  Leibniz international proceedings in informatics (LIPIcs) 66: 46 (2017)
  Publisher DOI
• Large independent sets in triangle-free planar graphs
  Dvořák, Zdeněk; Mnich, Matthias
  SIAM Journal on Discrete Mathematics (2017)
  Publisher DOI
• Polynomial kernels for weighted problems
  Etscheid, Michael; Kratsch, Stefan; Mnich, Matthias; Röglin, Heiko
  Journal of Computer and System Sciences (2017)
  Publisher DOI
• Stable marriage with covering constraints – a complete computational trichotomy
  Mnich, Matthias; Schlotter, Ildikó
  10th International Symposium on Algorithmic Game Theory (SAGT 2017)
  Publisher DOI

2016

• Linear kernels and linear-time algorithms for finding large cuts
  Etscheid, Michael; Mnich, Matthias
  27th International Symposium on Algorithms and Computation (ISAAC 2016)
  Open Access | Publisher DOI
• Parameterized complexity dichotomy for Steiner Multicut
  Bringmann, Karl; Hermelin, Danny; Mnich, Matthias; Leeuwen, Erik Jan van
  Journal of Computer and System Sciences (2016)
  Publisher DOI
• New algorithms for maximum disjoint paths based on tree-likeness
  Fleszar, Krzysztof; Mnich, Matthias; Spoerhase, Joachim
  24th European Symposium on Algorithms (ESA 2016)
  Publisher DOI
• Linear-time recognition of map graphs with outerplanar witness
  Mnich, Matthias; Rutter, Ignaz; Schmidt, Jens M.
  15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016) 53: 5.1-5.4 (2016
  Publisher DOI
• On routing disjoint paths in bounded treewidth graphs
  Ene, Alina; Mnich, Matthias; Pilipczuk, Marcin; Risteski, Andrej
  Leibniz International Proceedings in Informatics (LIPIcs) 53: 15 (2016)
  Publisher DOI
• New deterministic algorithms for solving parity games
  Mnich, Matthias; Röglin, Heiko; Rösner, Clemens
  Theoretical Informatics (LATIN 2016)
  Publisher DOI
• Lower bounds for locally highly connected graphs
  Adamaszek, Anna; Adamaszek, Michal; Mnich, Matthias; Schmidt, Jens M.
  Graphs and Combinatorics 32 : 1641-1650 (2016)
  Publisher DOI
• A 7/3-approximation for feedback vertex sets in tournaments
  Mnich, Matthias; Vassilevska Williams, Virginia; Végh, Lászlo A.
  Leibniz international proceedings in informatics (LIPIcs) 57: 67 (2016)
  Publisher DOI
• Improved bounds for minimal feedback vertex sets in tournaments
  Mnich, Matthias; Teutrine, Eva-Lotta
  11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
  Publisher DOI
• Polynomial kernels for deletion to classes of acyclic digraphs
  Mnich, Matthias; Leeuwen, Erik Jan van
  33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
  Open Access | Publisher DOI

2015

• Polynomial kernels for weighted problems
  Etscheid, Michael; Kratsch, Stefan; Mnich, Matthias; Röglin, Heiko
  Lecture notes in computer science 9235 LNCS: 287-298 (2015)
  Publisher DOI
• Max-Cut parameterized above the Edwards-Erdős bound
  Crowston, Robert; Jones, Mark; Mnich, Matthias
  Algorithmica (2015)
  Publisher DOI
• Parameterized complexity dichotomy for Steiner multicut
  Bringmann, Karl; Hermelin, Danny; Mnich, Matthias; Leeuwen, Erik Jan van
  Leibniz International Proceedings in Informatics (LIPIcs) 30: 157-170 (2015)
  Publisher DOI

2014

• Scheduling and fixed-parameter tractability
  Mnich, Matthias; Wiese, Andreas
  Mathematical Programming (2015)
  Publisher DOI
• Parameterized complexity of induced graph matching on claw-free graphs
  Hermelin, Danny; Mnich, Matthias; Leeuwen, Erik Jan van
  Algorithmica (2014)
  Publisher DOI
• Interval scheduling and colorful independent sets
  van Bevern, René; Mnich, Matthias; Niedermeier, Rolf; Weller, Mathias
  Journal of Scheduling (2014)
  Publisher DOI
• Large independent sets in triangle-free planar graphs
  Dvořák, Zdeněk; Mnich, Matthias
  22nd Annual European Symposium on Algorithms (ESA 2014)
  Publisher DOI
• Scheduling and fixed-parameter tractability
  Mnich, Matthias; Wiese, Andreas
  International Conference on Integer Programming and Combinatorial Optimization (IPCO 2014)
  Publisher DOI
• Social choice meets graph drawing : how to get subexponential time algorithms for ranking and drawing problems
  Fernau, Henning; Fomin, Fedor V.; Lokshtanov, Daniel; Mnich, Matthias; Philip, Geevarghese; Saurabh, Saket
  Tsinghua Science and Technology (2014)
  Publisher DOI
• Treewidth computation and kernelization in the parallel external memory model
  Jacob, Riko; Lieber, Tobias; Mnich, Matthias
  IFIP International Conference on Theoretical Computer Science (TCS 2014)
  Publisher DOI

2013

• Kernel and fast algorithm for dense triplet inconsistency
  Guillemot, Sylvain; Mnich, Matthias
  Theoretical Computer Science (2013)
  Publisher DOI

2012

• Feedback vertex sets in tournaments
  Gaspers, Serge; Mnich, Matthias
  Journal of Graph Theory (2012)
  Publisher DOI
• Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables
  Gutin, Gregory Z.; Iersel, Leo van; Mnich, Matthias; Yeo, Anders
  Journal of Computer and System Sciences (2012)
  Publisher DOI
• Beyond Max-Cut: λ-extendible properties parameterized above the Poljak-Turzík bound
  Mnich, Matthias; Philip, Geevarghese; Saurabh, Saket; Suchý, Ondřej
  Annual Conference on Foundations of Software Technology and Theoretical Computer Science (2012)
  Publisher DOI
• Bisections above tight lower bounds
  Mnich, Matthias; Zenklusen, Rico
  International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2012)
  Publisher DOI
• Induced matchings in subcubic planar graphs
  Kang, Ross J.; Mnich, Matthias; Müller, Tobias
  SIAM Journal on Discrete Mathematics (2012)
  Publisher DOI
• Interval scheduling and colorful independent sets
  van Bevern, René; Mnich, Matthias; Niedermeier, Rolf; Weller, Mathias
  International Symposium on Algorithms and Computation (ISAAC 2012)
  Publisher DOI
• Max-Cut parameterized above the Edwards-Erdős bound
  Crowston, Robert; Jones, Mark; Mnich, Matthias
  International Colloquium on Automata, Languages and Programming (ICALP 2012)
  Publisher DOI
• Parameterized complexity of induced H-matching on claw-free graphs
  Hermelin, Danny; Mnich, Matthias; Leeuwen, Erik Jan van
  European Symposium on Algorithms (ESA 2012)
  Publisher DOI

2011

• Allemaal op een rijtje
  Mnich, Matthias
  Nieuw Archief voor Wiskunde (2011)
  
• Book review "Exact Exponential Algorithms" Springer Verlag, Berlin (2010)
  Mnich, Matthias
  Operations Research Letters (2011)
  Publisher DOI
• Domination when the stars are out
  Hermelin, Danny; Mnich, Matthias; Leeuwen, Erik Jan van; Woeginger, Gerhard
  International Colloquium on Automata, Languages, and Programming (ICALP 2011)
  Publisher DOI
• Planar $k$-path in subexponential time and polynomial space
  Lokshtanov, Daniel; Mnich, Matthias; Saurabh, Saket
  International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2011)
  Publisher DOI
• Ranking and drawing in subexponential time
  Fernau, Henning; Fomin, Fedor V.; Lokshtanov, Daniel; Mnich, Matthias; Philip, Geevarghese; Saurabh, Saket
  International Workshop on Combinatorial Algorithms IWOCA (2010)
  Publisher DOI

2010

• Induced matchings in subcubic planar graphs
  Kang, Ross J.; Mnich, Matthias; Müller, Tobias
  18th Annual European Symposium on Algorithms (ESA 2010)
  Publisher DOI
• All ternary permutation constraint satisfaction problems parameterized above average have kernels with quadratic numbers of variables
  Gutin, Gregory Z.; Iersel, Leo van; Mnich, Matthias; Yeo, Anders
  18th Annual European Symposium on Algorithms (ESA 2010)
  Publisher DOI
• Betweenness parameterized above tight lower bound
  Gutin, Gregory Z.; Kim, Eun Jung; Mnich, Matthias; Yeo, Anders
  Journal of Computer and System Sciences (2010)
  Publisher DOI
• Feedback vertex sets in tournaments
  Gaspers, Serge; Mnich, Matthias
  European Symposium on Algorithms (ESA 2010)
  Publisher DOI
• Kernel and fast algorithm for dense triplet inconsistency
  Guillemot, Sylvain; Mnich, Matthias
  International Conference on Theory and Applications of Models of Computation (TAMC 2010)
  Publisher DOI

2009

• The complexity ecology of parameters: An illustration using bounded max leaf number
  Fellows, Michael; Lokshtanov, Daniel; Misra, Neeldhara; Mnich, Matthias; Rosamond, Frances; Saurabh, Saket
  Theory of Computing Systems (2009).
  Publisher DOI
• Linear kernel for planar connected dominating set
  Lokshtanov, Daniel; Mnich, Matthias; Saurabh, Saket
  International Conference on Theory and Applications of Models of Computation (TAMC 2009)
  Publisher DOI
• Uniqueness, intractability and exact algorithms : reflections on level-k phylogenetic networks
  Iersel, Leo van; Kelk, Steven; Mnich, Matthias
  Journal of Bioinformatics and Computational Biology (2009)
  Publisher DOI