Kernelization for big data (2014 - 2021) funded by Deutsche Forschungsgemeinschaft (DFG) Multivariate algorithms for high-multiplicity scheduling (2017 - 2021) funded by Deutsche Forschungsgemeinschaft (DFG) A fixed-parameter approach towards combinatorial optimization (2019 - 2021) funded by German Academic Exchange Service (DAAD) Simultaneous approximation of multi-criteria optimization problems (2021 - 2022) funded by German Academic Exchange Service (DAAD) New algorithmic approaches to macromolecular crystallographic analysis (2021 - 2024) funded by DASHH Data Science in Hamburg - Helmholtz Graduate School for the Structure of Matter Data-driven decentralized energy trading (2021 - 2024) funded by ahoi.digital
PC member of FCT 2023 (International Symposium on Fundamentals in Computation Theory) PC member of SEA 2023 (International Symposium on Experimental Algorithms) PC member of STACS 2023 (Symposium on Theoretical Aspects of Computer Science) PC member of WAOA 2021 (Workshop on Approximation and Online Algorithms) PC member of IJCAI 2020 (International Joint Conference on Artificial Intelligence) PC member of IJCAI 2019 (International Joint Conference on Artificial Intelligence) PC member of ARDA 2019 (Advances in Reoptimization and Dynamic Algorithms) PC member of Euro-Par 2019 (International European Conference on Parallel and Distributed Computing) PC member of SWAT 2018 (Scandinavian Symposium and Workshops on Algorithm Theory) PC member of IJCAI 2018 (International Joint Conference on Artificial Intelligence) PC member of AAAI 2018 (AAAI Conference on Artificial Intelligence)
2023
2022
A survey on graph problems parameterized above and below guaranteed values
Gutin, Gregory Z.; Mnich, Matthias
arXiv: 2207.12278 (2022)
Open Access
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
Approximations for many-visits multiple traveling salesman problems
Bérczi, Kristóf; Mnich, Matthias; Vincze, Roland
Omega - The International Journal of Management Science (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
Exponentially faster fixed-parameter algorithms for high-multiplicity scheduling
Fischer, David; Golak, Julian; Mnich, Matthias
arXiv: 2203.03600 (2022)
Open Access
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
High multiplicity N-fold IP via configuration LP
Knop, Dušan; Koutecký, Martin; Levin, Asaf; Mnich, Matthias; Onn, Shmuel
Mathematical Programming (2022)
Open Access
|
Publisher DOI
Parameterized algorithms for generalizations of directed feedback vertex set
Göke, Alexander; Marx, Dániel; Mnich, Matthias
Discrete Optimization (2022)
Open Access
|
Publisher DOI
2021
Efficient approximations for many-visits multiple traveling salesman problems
Bérczi, Kristóf; Mnich, Matthias; Vincze, Roland
arXiv: 2201.02054 (2021)
Open Access
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
Reachability switching games
Fearnley, John; Gairing, Martin; Mnich, Matthias; Savani, Rahul
Logical Methods in Computer Science (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
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
2020
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
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
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
Dense Steiner problems: approximation algorithms and inapproximability
Karpinski, Marek; Lewandowski, Mateusz; Meesum, Syed Mohammad; Mnich, Matthias
arXiv:2004.14102 (2020)
Voting and bribing in single-exponential time
Knop, Dušan; Koutecký, Martin; Mnich, Matthias
ACM Transactions on Economics and Computation (2020)
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
Odd multiway cut in directed acyclic graphs
Chandrasekaran, Karthekeyan; Mnich, Matthias; Mozaffari, Sahand
SIAM Journal on Discrete Mathematics (2020)
Publisher DOI
Dynamic parameterized problems and algorithms
Alman, Josh; Mnich, Matthias; Vassilevska Williams, Virginia
ACM Transactions on Algorithms (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
Stable matchings with covering constraints: a complete computational trichotomy
Mnich, Matthias; Schlotter, Ildikó
Algorithmica (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
Combinatorial n-fold integer programming and applications
Knop, Dušan; Koutecký, Martin; Mnich, Matthias
Mathematical Programming 184 (1-2): (2020-11-01)
Open Access
|
Publisher DOI
2019
A time- and space-optimal algorithm for the many-visits TSP
Berger, André; Kozma, László; Mnich, Matthias; Vincze, Roland
30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2019)
Open Access
|
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
Domination when the stars are out
Hermelin, Danny; Mnich, Matthias; Leeuwen, Erik Jan van; Woeginger, Gerhard
ACM Transactions on Algorithms (2019)
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
Multitype integer monoid optimization and applications
Knop, Dušan; Koutecký, Martin; Levin, Asaf; Mnich, Matthias; Onn, Shmuel
arXiv:1909.07326 (2019)
Open Access
Single machine batch scheduling to minimize the weighted number of tardy jobs
Hermelin, Danny; Mnich, Matthias; Omlor, Simon
arxiv:1911.12350 (2019)
Open Access
Resolving infeasibility of linear systems: a parameterized approach
Göke, Alexander; Mendoza Cadena, Lydia Mirabel; Mnich, Matthias
14th International Symposium on Parameterized and Exact Computation (IPEC 2019)
Open Access
|
Publisher DOI
2018
A unifying framework for manipulation problems
Knop, Dušan; Koutecký, Martin; Mnich, Matthias
17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2018)
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
New algorithms for maximum disjoint paths based on tree-likeness
Fleszar, Krzysztof; Mnich, Matthias; Spoerhase, Joachim
Mathematical Programming (2018)
Publisher DOI
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
Linear-time recognition of map graphs with outerplanar witness
Mnich, Matthias; Rutter, Ignaz; Schmidt, Jens M.
Discrete Optimization (2018)
Publisher DOI
New deterministic algorithms for solving parity games
Mnich, Matthias; Röglin, Heiko; Rösner, Clemens
Discrete Optimization (2018)
Publisher DOI
Parameterized complexity of machine scheduling: 15 open problems
Mnich, Matthias; van Bevern, René
Computers (2018)
Publisher DOI
2017
Large independent sets in triangle-free planar graphs
Dvořák, Zdeněk; Mnich, Matthias
SIAM Journal on Discrete Mathematics (2017)
Publisher DOI
Voting and bribing in single-exponential time
Knop, Dušan; Koutecký, Martin; Mnich, Matthias
34th Symposium on Theoretical Aspects of Computer Science (STACS 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
Polynomial kernels for weighted problems
Etscheid, Michael; Kratsch, Stefan; Mnich, Matthias; Röglin, Heiko
Journal of Computer and System Sciences (2017)
Publisher DOI
Polynomial kernels for deletion to classes of acyclic digraphs
Mnich, Matthias; Leeuwen, Erik Jan van
Discrete Optimization (2017)
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
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
Big data algorithms beyond machine learning
Mnich, Matthias
Künstliche Intelligenz 32 (1): 9-17 (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
Improved bounds for minimal feedback vertex sets in tournaments
Mnich, Matthias; Teutrine, Eva Lotta
Journal of Graph Theory (2018)
Open Access
|
Publisher DOI
2016
On routing disjoint paths in bounded treewidth graphs
Ene, Alina; Mnich, Matthias; Pilipczuk, Marcin; Risteski, Andrej
15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 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
A 7/3-approximation for feedback vertex sets in tournaments
Mnich, Matthias; Vassilevska Williams, Virginia; Végh, Lászlo A.
24th Annual European Symposium on Algorithms (ESA 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
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
New deterministic algorithms for solving parity games
Mnich, Matthias; Röglin, Heiko; Rösner, Clemens
Theoretical Informatics (LATIN 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)
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
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
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
2015
Parameterized complexity dichotomy for Steiner multicut
Bringmann, Karl; Hermelin, Danny; Mnich, Matthias; Leeuwen, Erik Jan van
32nd Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Publisher DOI
Max-Cut parameterized above the Edwards-Erdős bound
Crowston, Robert; Jones, Mark; Mnich, Matthias
Algorithmica (2015)
Publisher DOI
Polynomial kernels for weighted problems
Etscheid, Michael; Kratsch, Stefan; Mnich, Matthias; Röglin, Heiko
40th International Symposium on Mathematical Foundations of Computer Science (MFCS 2015)
Publisher DOI
2014
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
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
Interval scheduling and colorful independent sets
van Bevern, René; Mnich, Matthias; Niedermeier, Rolf; Weller, Mathias
Journal of Scheduling (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
Parameterized complexity of induced graph matching on claw-free graphs
Hermelin, Danny; Mnich, Matthias; Leeuwen, Erik Jan van
Algorithmica (2014)
Publisher DOI
Scheduling and fixed-parameter tractability
Mnich, Matthias; Wiese, Andreas
Mathematical Programming (2015)
Publisher DOI
2013
2012
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
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
Bisections above tight lower bounds
Mnich, Matthias; Zenklusen, Rico
International Workshop on Graph-Theoretic Concepts in Computer Science (WG 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
Induced matchings in subcubic planar graphs
Kang, Ross J.; Mnich, Matthias; Müller, Tobias
SIAM Journal on Discrete Mathematics (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
Feedback vertex sets in tournaments
Gaspers, Serge; Mnich, Matthias
Journal of Graph Theory (2012)
Publisher DOI
2011
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
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
Book review "Exact Exponential Algorithms" Springer Verlag, Berlin (2010)
Mnich, Matthias
Operations Research Letters (2011)
Publisher DOI
Allemaal op een rijtje
Mnich, Matthias
Nieuw Archief voor Wiskunde (2011)
2010
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
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
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
Induced matchings in subcubic planar graphs
Kang, Ross J.; Mnich, Matthias; Müller, Tobias
18th Annual European Symposium on Algorithms (ESA 2010)
Publisher DOI
2009
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
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