Matthias Mnich

According to our database, Matthias Mnich authored at least 83 papers between 2009 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2024

Approximating Sparsest Cut in Low-treewidth Graphs via Combinatorial Diameter.

Parinya Chalermsook, Matthias Kaul, Matthias Mnich, Joachim Spoerhase, Sumedha Uniyal, Daniel Vaz

ACM Trans. Algorithms, January, 2024

New Support Size Bounds and Proximity Bounds for Integer Linear Programming.

Sebastian Berndt, Matthias Mnich, Tobias Stamm

Proceedings of the SOFSEM 2024: Theory and Practice of Computer Science, 2024

2023

High-multiplicity N-fold IP via configuration LP.

Dusan Knop, Martin Koutecký, Asaf Levin, Matthias Mnich, Shmuel Onn

Math. Program., 2023

No Polynomial Kernels for Knapsack.

Klaus Heeger, Danny Hermelin, Matthias Mnich, Dvir Shabtay

CoRR, 2023

New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines.

Sebastian Berndt, Hauke Brinkop, Klaus Jansen, Matthias Mnich, Tobias Stamm

Proceedings of the 34th International Symposium on Algorithms and Computation, 2023

Checkpoint Placement for Systematic Fault-Injection Campaigns.

Christian Dietrich, Tim-Marek Thomas, Matthias Mnich

Proceedings of the IEEE/ACM International Conference on Computer Aided Design, 2023

Improved Approximations for Vector Bin Packing via Iterative Randomized Rounding.

Ariel Kulik, Matthias Mnich, Hadas Shachnai

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

A (3/2 + ε)-Approximation for Multiple TSP with a Variable Number of Depots.

Max Deppert, Matthias Kaul, Matthias Mnich

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth.

Benjamin Bergougnoux, Vera Chekan, Robert Ganian, Mamadou Moustapha Kanté, Matthias Mnich, Sang-il Oum, Michal Pilipczuk, Erik Jan van Leeuwen

Proceedings of the 31st Annual European Symposium on Algorithms, 2023

2022

Hitting Weighted Even Cycles in Planar Graphs.

Alexander Göke, Jochen Könemann, Matthias Mnich, Hao Sun

SIAM J. Discret. Math., December, 2022

A 3/2-Approximation for the Metric Many-Visits Path TSP.

Kristóf Bérczi, Matthias Mnich, Roland Vincze

SIAM J. Discret. Math., December, 2022

Parameterized algorithms for generalizations of Directed Feedback Vertex Set.

Alexander Göke, Dániel Marx, Matthias Mnich

Discret. Optim., 2022

Resolving Infeasibility of Linear Systems: A Parameterized Approach.

Kristóf Bérczi, Alexander Göke, Lydia Mirabel Mendoza Cadena, Matthias Mnich

CoRR, 2022

A Survey on Graph Problems Parameterized Above and Below Guaranteed Values.

Gregory Z. Gutin, Matthias Mnich

CoRR, 2022

An Asymptotic (4/3+ε)-Approximation for the 2-Dimensional Vector Bin Packing Problem.

Ariel Kulik, Matthias Mnich, Hadas Shachnai

CoRR, 2022

Exponentially faster fixed-parameter algorithms for high-multiplicity scheduling.

David Fischer, Julian Golak, Matthias Mnich

CoRR, 2022

Efficient Approximations for Many-Visits Multiple Traveling Salesman Problems.

Kristóf Bérczi, Matthias Mnich, Roland Vincze

CoRR, 2022

Recent Advances in Practical Data Reduction.

Faisal N. Abu-Khzam, Sebastian Lamm, Matthias Mnich, Alexander Noe, Christian Schulz, Darren Strash

Proceedings of the Algorithms for Big Data - DFG Priority Program 1736, 2022

2021

Parameterized complexity of configuration integer programs.

Dusan Knop, Martin Koutecký, Asaf Levin, Matthias Mnich, Shmuel Onn

Oper. Res. Lett., 2021

Reachability Switching Games.

John Fearnley, Martin Gairing, Matthias Mnich, Rahul Savani

Log. Methods Comput. Sci., 2021

2020

Voting and Bribing in Single-Exponential Time.

Dusan Knop, Martin Koutecký, Matthias Mnich

ACM Trans. Economics and Comput., 2020

Time- and Space-optimal Algorithm for the Many-visits TSP.

André Berger, László Kozma, Matthias Mnich, Roland Vincze

ACM Trans. Algorithms, 2020

Dynamic Parameterized Problems and Algorithms.

Josh Alman, Matthias Mnich, Virginia Vassilevska Williams

ACM Trans. Algorithms, 2020

Odd Multiway Cut in Directed Acyclic Graphs.

Karthekeyan Chandrasekaran, Matthias Mnich, Sahand Mozaffari

SIAM J. Discret. Math., 2020

Combinatorial n-fold integer programming and applications.

Dusan Knop, Martin Koutecký, Matthias Mnich

Math. Program., 2020

On the complexity of solving a decision problem with flow-depending costs: The case of the IJsselmeer dikes.

Aida Abiad, Sander Gribling, Domenico Lahaye, Matthias Mnich, Guus Regts, Lluís Vena, Gerard Verweij, Peter J. Zwaneveld

Discret. Optim., 2020

Recent Advances in Practical Data Reduction.

Faisal N. Abu-Khzam, Sebastian Lamm, Matthias Mnich, Alexander Noe, Christian Schulz, Darren Strash

CoRR, 2020

Dense Steiner problems: Approximation algorithms and inapproximability.

Marek Karpinski, Mateusz Lewandowski, Syed Mohammad Meesum, Matthias Mnich

CoRR, 2020

Stable Matchings with Covering Constraints: A Complete Computational Trichotomy.

Matthias Mnich, Ildikó Schlotter

Algorithmica, 2020

Solving Packing Problems with Few Small Items Using Rainbow Matchings.

Max Bannach, Sebastian Berndt, Marten Maack, Matthias Mnich, Alexandra Lassota, Malin Rau, Malte Skambath

Proceedings of the 45th International Symposium on Mathematical Foundations of Computer Science, 2020

Hitting Long Directed Cycles Is Fixed-Parameter Tractable.

Alexander Göke, Dániel Marx, Matthias Mnich

Proceedings of the 47th International Colloquium on Automata, Languages, and Programming, 2020

Engineering Kernelization for Maximum Cut.

Damir Ferizovic, Demian Hespe, Sebastian Lamm, Matthias Mnich, Christian Schulz, Darren Strash

Proceedings of the Symposium on Algorithm Engineering and Experiments, 2020

2019

Domination When the Stars Are Out.

Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen, Gerhard J. Woeginger

ACM Trans. Algorithms, 2019

Single Machine Batch Scheduling to Minimize the Weighted Number of Tardy Jobs.

Danny Hermelin, Matthias Mnich, Simon Omlor

CoRR, 2019

Degree-Bounded Generalized Polymatroids and Approximating the Metric Many-Visits TSP.

Kristóf Bérczi, André Berger, Matthias Mnich, Roland Vincze

CoRR, 2019

Multitype Integer Monoid Optimization and Applications.

Dusan Knop, Martin Koutecký, Asaf Levin, Matthias Mnich, Shmuel Onn

CoRR, 2019

Resolving Infeasibility of Linear Systems: A Parameterized Approach.

Alexander Göke, Lydia Mirabel Mendoza Cadena, Matthias Mnich

Proceedings of the 14th International Symposium on Parameterized and Exact Computation, 2019

2018

New algorithms for maximum disjoint paths based on tree-likeness.

Krzysztof Fleszar, Matthias Mnich, Joachim Spoerhase

Math. Program., 2018

Big data algorithms beyond machine learning.

Matthias Mnich

Künstliche Intell., 2018

Improved bounds for minimal feedback vertex sets in tournaments.

Matthias Mnich, Eva-Lotta Teutrine

J. Graph Theory, 2018

Improved integrality gap upper bounds for traveling salesperson problems with distances one and two.

Matthias Mnich, Tobias Mömke

Eur. J. Oper. Res., 2018

Linear-time recognition of map graphs with outerplanar witness.

Matthias Mnich, Ignaz Rutter, Jens M. Schmidt

Discret. Optim., 2018

New deterministic algorithms for solving parity games.

Matthias Mnich, Heiko Röglin, Clemens Rösner

Discret. Optim., 2018

Time- and space-optimal algorithms for the many-visits TSP.

André Berger, László Kozma, Matthias Mnich, Roland Vincze

CoRR, 2018

Parameterized complexity of machine scheduling: 15 open problems.

Matthias Mnich, René van Bevern

Comput. Oper. Res., 2018

Linear Kernels and Linear-Time Algorithms for Finding Large Cuts.

Michael Etscheid, Matthias Mnich

Algorithmica, 2018

New Approximation Algorithms for (1, 2)-TSP.

Anna Adamaszek, Matthias Mnich, Katarzyna Paluch

Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, 2018

A Unifying Framework for Manipulation Problems.

Dusan Knop, Martin Koutecký, Matthias Mnich

Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, 2018

2017

Large Independent Sets in Triangle-Free Planar Graphs.

Zdenek Dvorák, Matthias Mnich

SIAM J. Discret. Math., 2017

Polynomial kernels for weighted problems.

Michael Etscheid, Stefan Kratsch, Matthias Mnich, Heiko Röglin

J. Comput. Syst. Sci., 2017

Polynomial kernels for deletion to classes of acyclic digraphs.

Matthias Mnich, Erik Jan van Leeuwen

Discret. Optim., 2017

Stable Marriage with Covering Constraints-A Complete Computational Trichotomy.

Matthias Mnich, Ildikó Schlotter

Proceedings of the Algorithmic Game Theory - 10th International Symposium, 2017

2016

Parameterized complexity dichotomy for Steiner Multicut.

Karl Bringmann, Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen

J. Comput. Syst. Sci., 2016

Lower Bounds for Locally Highly Connected Graphs.

Anna Adamaszek, Michal Adamaszek, Matthias Mnich, Jens M. Schmidt

Graphs Comb., 2016

Large Independent Sets in Subquartic Planar Graphs.

Matthias Mnich

Proceedings of the WALCOM: Algorithms and Computation - 10th International Workshop, 2016

On Routing Disjoint Paths in Bounded Treewidth Graphs.

Alina Ene, Matthias Mnich, Marcin Pilipczuk, Andrej Risteski

Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory, 2016

A 7/3-Approximation for Feedback Vertex Sets in Tournaments.

Matthias Mnich, Virginia Vassilevska Williams, László A. Végh

Proceedings of the 24th Annual European Symposium on Algorithms, 2016

2015

Interval scheduling and colorful independent sets.

René van Bevern, Matthias Mnich, Rolf Niedermeier, Mathias Weller

J. Sched., 2015

Scheduling and fixed-parameter tractability.

Matthias Mnich, Andreas Wiese

Math. Program., 2015

Max-Cut Parameterized Above the Edwards-Erdős Bound.

Robert Crowston, Mark Jones, Matthias Mnich

Algorithmica, 2015

When Does Schwartz Conjecture Hold?

Matthias Mnich, Yash Raj Shrestha, Yongjie Yang

Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, 2015

2014

Beyond Max-Cut: λ-extendible properties parameterized above the Poljak-Turzík bound.

Matthias Mnich, Geevarghese Philip, Saket Saurabh, Ondrej Suchý

J. Comput. Syst. Sci., 2014

Parameterized Complexity of Induced Graph Matching on Claw-Free Graphs.

Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen

Algorithmica, 2014

Treewidth Computation and Kernelization in the Parallel External Memory Model.

Riko Jacob, Tobias Lieber, Matthias Mnich

Proceedings of the Theoretical Computer Science, 2014

2013

Kernel and fast algorithm for dense triplet inconsistency.

Sylvain Guillemot, Matthias Mnich

Theor. Comput. Sci., 2013

Feedback Vertex Sets in Tournaments.

Serge Gaspers, Matthias Mnich

J. Graph Theory, 2013

Scheduling Meets Fixed-Parameter Tractability.

Matthias Mnich, Andreas Wiese

CoRR, 2013

Improved integrality gap upper bounds for TSP with distances one and two.

Matthias Mnich, Tobias Mömke

CoRR, 2013

2012

Induced Matchings in Subcubic Planar Graphs.

Ross J. Kang, Matthias Mnich, Tobias Müller

SIAM J. Discret. Math., 2012

Every ternary permutation constraint satisfaction problem parameterized above average has a kernel with a quadratic number of variables.

Gregory Z. Gutin, Leo van Iersel, Matthias Mnich, Anders Yeo

J. Comput. Syst. Sci., 2012

Bisections above Tight Lower Bounds.

Matthias Mnich, Rico Zenklusen

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2012

Beyond Max-Cut: lambda-Extendible Properties Parameterized Above the Poljak-Turzik Bound.

Matthias Mnich, Geevarghese Philip, Saket Saurabh, Ondrej Suchý

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2012

Parameterized Complexity of Induced H-Matching on Claw-Free Graphs.

Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen

Proceedings of the Algorithms - ESA 2012, 2012

2011

A linear kernel for planar connected dominating set.

Daniel Lokshtanov, Matthias Mnich, Saket Saurabh

Theor. Comput. Sci., 2011

Book review.

Matthias Mnich

Oper. Res. Lett., 2011

Planar k-Path in Subexponential Time and Polynomial Space.

Daniel Lokshtanov, Matthias Mnich, Saket Saurabh

Proceedings of the Graph-Theoretic Concepts in Computer Science, 2011

2010

Betweenness parameterized above tight lower bound.

Gregory Z. Gutin, Eun Jung Kim, Matthias Mnich, Anders Yeo

J. Comput. Syst. Sci., 2010

All Ternary Permutation Constraint Satisfaction Problems Parameterized Above Average Have Polynomial Kernels

Gregory Z. Gutin, Leo van Iersel, Matthias Mnich, Anders Yeo

CoRR, 2010

Ranking and Drawing in Subexponential Time.

Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov, Matthias Mnich, Geevarghese Philip, Saket Saurabh

Proceedings of the Combinatorial Algorithms - 21st International Workshop, 2010

All Ternary Permutation Constraint Satisfaction Problems Parameterized above Average Have Kernels with Quadratic Numbers of Variables.

Gregory Z. Gutin, Leo van Iersel, Matthias Mnich, Anders Yeo

Proceedings of the Algorithms, 2010

2009

The Complexity Ecology of Parameters: An Illustration Using Bounded Max Leaf Number.

Michael R. Fellows, Daniel Lokshtanov, Neeldhara Misra, Matthias Mnich, Frances A. Rosamond, Saket Saurabh

Theory Comput. Syst., 2009

Uniqueness, Intractability and Exact Algorithms: Reflections on Level-k Phylogenetic Networks.

Leo van Iersel, Steven Kelk, Matthias Mnich

J. Bioinform. Comput. Biol., 2009

Ordinal Embedding Relaxations Parameterized Above Tight Lower Bound

Gregory Z. Gutin, Eun Jung Kim, Matthias Mnich, Anders Yeo

CoRR, 2009