ALGO: Research

Research

The members of the institute perform research in combinatorial algorithms, discrete mathematics, and computational complexity.

The research is generously funded by TUHH, the German Science Foundation (DFG) and the German Academic Exchange Service (DAAD).

The primary outlet of the produced research results are publications in peer-reviewed scientific journals and peer-reviewed scientific conference proceedings.

Current publication records may be selected using the side menu on the left. The following is a fixed list of representative publications.

All publications of the Institute for Algorithms and Complexity

Representative publications

Ariel Kulik, Matthias Mnich, Hadas Shachnai:
Improved approximations for vector bin packing via iterative randomized rounding
FOCS 2023
Max Deppert, Matthias Kaul, Matthias Mnich:
A (3/2+ε)-approximation for multiple TSP with a variable number of depots
ESA 2023
Alexander Göke, Dániel Marx, Matthias Mnich:
Hitting long directed cycles is fixed-parameter tractable
ICALP 2020
André Berger, László Kozma, Matthias Mnich, Roland Vincze:
Time- and space-optimal algorithms for the many-visits TSP
SODA 2019
ACM Transactions on Algorithms
Presentation at Hausdorff Workshop on Combinatorial Optimization
Anna Adamaszek, Matthias Mnich, Katarzyna Paluch:
New approximation algorithms for (1,2)-TSP
ICALP 2018
John Fearnley, Martin Gairing, Matthias Mnich, Rahul Savani:
Reachability switching games
ICALP 2018
Martin Koutecký, Dušan Knop, Matthias Mnich:
Combinatorial n-fold integer programming and applications
ESA 2017
Mathematical Programming
Josh Alman, Matthias Mnich, Virginia Vassilevska Williams:
Dynamic parameterized problems and algorithms
ICALP 2017
ACM Transactions on Algorithms
Krzysztof Fleszar, Matthias Mnich, Joachim Spoerhase:
New algorithms for maximum disjoint paths based on tree-likeness
ESA 2016
Mathematical Programming
Matthias Mnich, Virginia Vassilevska Williams, László A. Végh:
A 7/3-approximation for feedback vertex sets in tournaments
ESA 2016
Presentation at Hausdorff Trimester in Combinatorial Optimization
Zdeněk Dvořák, Matthias Mnich:
Large independent sets in triangle-free planar graphs
ESA 2014
SIAM Journal on Discrete Mathematics
Matthias Mnich, Andreas Wiese:
Scheduling and fixed-parameter tractability
IPCO 2014
Mathematical Programming
Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen:
Parameterized complexity of induced H-matching on claw-free graphs
ESA 2012
Algorithmica
Robert Crowston, Mark Jones, Matthias Mnich:
Max-cut parameterized above the Edwards-Erdős-bound
ICALP 2012
Algorithmica
Danny Hermelin, Matthias Mnich, Erik Jan van Leeuwen, Gerhard J. Woeginger:
Domination when the stars are out
ICALP 2011
ACM Transactions on Algorithms
Gregory Gutin, Leo van Iersel, Matthias Mnich, Anders Yeo:
All ternary permutation constraint satisfaction problems parameterized above average have polynomial kernels
ESA 2010
Journal of Computer and System Sciences
Serge Gaspers, Matthias Mnich:
Feedback vertex sets in tournaments
ESA 2010
Journal of Graph Theory
Ross Kang, Matthias Mnich, Tobias Müller:
Induced matchings in subcubic planar graphs
ESA 2010
SIAM Journal on Discrete Mathematics

All Publications

All publications

2024

Chalermsook, Parinya; Kaul, Matthias; Mnich, Matthias; Spoerhase, Joachim; Uniyal, Sumedha; Vaz, Daniel
Approximating sparsest cut in low-treewidth graphs via combinatorial diameter
ACM Transactions in Algorithms (2024)
Publisher DOI
Berndt, Sebastian; Mnich, Matthias; Stamm, Tobias
New support bounds and proximity bounds for integer linear programming
Publisher DOI

2023

Kulik, Ariel; Mnich, Matthias; Shachnai, Hadas
Improved Approximations for Vector Bin Packing via Iterative Randomized Rounding
IEEE Annual Symposium on Foundations of Computer Science (FOCS 2023)
Publisher DOI
Deppert, Max; Kaul, Matthias; Mnich, Matthias
A (3/2 + ε)-Approximation for multiple TSP with a variable number of depots
European Symposium on Algorithms (ESA 2023)
Open Access | Publisher DOI
Knop, Dušan; Koutecký, Martin; Levin, Asaf; Mnich, Matthias; Onn, Shmuel
High multiplicity N-fold IP via configuration LP
Mathematical Programming (2023)
Open Access | Publisher DOI
Galby, Esther; Munaro, Andrea; Yang, Shizhou
Polynomial-Time Approximation Schemes for Independent Packing Problems on Fractionally Tree-Independence-Number-Fragile Graphs
International Symposium on Computational Geometry (SoCG 2023)
Open Access | Publisher DOI
Fischer, David Simon; Györgyi, Péter
Approximation algorithms for coupled task scheduling minimizing the sum of completion times
Annals of Operations Research (2023)
Open Access | Publisher DOI
Bérczi, Kristóf; Mnich, Matthias; Vincze, Roland
Approximations for many-visits multiple traveling salesman problems
Omega : the international journal of management science (2023)
Open Access | Publisher DOI
Galby, Esther
The complexity of blocking (semi)total dominating sets with edge contractions
Theoretical Computer Science (2023)
Publisher DOI
Abu-Khzam, Faisal N.; Lamm, Sebastian; Mnich, Matthias; Noe, Alexander; Schulz, Christian; Strash, Darren
Recent advances in practical data reduction
Algorithms for Big Data (2023)
Open Access | Publisher DOI
Dietrich, Christian; Thomas, Tim-Marek; Mnich, Matthias
Checkpoint placement for systematic fault-injection campaigns
IEEE/ACM International Conference on Computer-Aided Design (ICCAD 2023)
Open Access | Publisher DOI
Berndt, Sebastian; Brinkop, Hauke; Jansen, Klaus; Mnich, Matthias; Stamm, Tobias
New support size bounds for integer programming, applied to makespan minimization on uniformly related machines
International Symposium on Algorithms and Computation (ISAAC 2023)
Open Access | Publisher DOI
Bergougnoux, Benjamin; Chekan, Vera; Ganian, Robert; Kanté, Mamadou Moustapha; Mnich, Matthias; Oum, Sang-il; Pilipczuk, Michał; Leeuwen, Erik Jan van
Space-efficient parameterized algorithms on graphs of low shrubdepth
European Symposium on Algorithms (ESA 2023)
Open Access | Publisher DOI

2022

Göke, Alexander; Marx, Dániel; Mnich, Matthias
Parameterized algorithms for generalizations of directed feedback vertex set  
Discrete Optimization (2022)
Open Access | Publisher DOI
Galby, Esther; Marx, Dániel; Schepper, Philipp; Sharma, Roohani; Tale, Prafullkumar
Domination and cut problems on chordal graphs with bounded leafage
International Symposium on Parameterized and Exact Computation (IPEC 2022)
Open Access | Publisher DOI
Kulik, Ariel; Mnich, Matthias; Shachnai, Hadas
An asymptotic (4/3+epsilon)-approximation for the 2-dimensional vector bin packing problem
arXiv: 2205.12828 (2022)
Open Access | Publisher DOI
Fischer, David; Golak, Julian; Mnich, Matthias
Exponentially faster fixed-parameter algorithms for high-multiplicity scheduling
arXiv: 2203.03600 (2022)
Open Access | Publisher DOI
Golak, Julian; Defryn, Christof; Grigoriev, Alexander
Optimizing fuel consumption on inland waterway networks : local search heuristic for lock scheduling
Omega : the international journal of management science (2022)
Open Access | Publisher DOI
Codazzi, Laura; Colombi, Alessandro; Gianella, Matteo; Argiento, Raffaele; Paci, Lucia; Pini, Alessia
Gaussian graphical modeling for spectrometric data analysis
Computational Statistics and Data Analysis (2022)
Open Access | Publisher DOI
Bérczi, Kristóf; Mnich, Matthias; Vincze, Roland
A 3/2-approximation for the metric many-visits path TSP
SIAM Journal on Discrete Mathematics (2022)
Open Access | Publisher DOI
Gutin, Gregory Z.; Mnich, Matthias
A survey on graph problems parameterized above and below guaranteed values
arXiv: 2207.12278 (2022)
Open Access | Publisher DOI
Vincze, Roland
Exact and approximation algorithms for many-visits travelling salesperson problems
Technische Universität Hamburg (2022)
Open Access
Göke, Alexander; Koenemann, Jochen; Mnich, Matthias; Sun, Hao
Hitting weighted even cycles in planar graphs
SIAM Journal on Discrete Mathematics (2022)
Open Access | Publisher DOI

2021

Knop, Dušan; Koutecký, Martin; Levin, Asaf; Mnich, Matthias; Onn, Shmuel
Parameterized complexity of configuration integer programs
Operations Research Letters (2021)
Open Access | Publisher DOI
Göke, Alexander; Koenemann, Jochen; Mnich, Matthias; Sun, Hao
Hitting weighted even cycles in planar graphs
International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX 2021)
Open Access | Publisher DOI
Lo, On-Hei Solomon; Schmidt, Jens M.
Cycle spectra of contraction-critically 4-connected planar graphs
Graphs and Combinatorics (2021)
Publisher DOI
Fearnley, John; Gairing, Martin; Mnich, Matthias; Savani, Rahul
Reachability switching games
Logical Methods in Computer Science (2021)
Open Access | Publisher DOI
Fabrici, Igor; Harant, Jochen; Mohr, Samuel; Schmidt, Jens M.
Circumference of essentially 4-connected planar triangulations
Journal of Graph Algorithms and Applications (2021)
Open Access | Publisher DOI
Chalermsook, Parinya; Kaul, Matthias; Mnich, Matthias; Spoerhase, Joachim; Uniyal, Sumedha; Vaz, Daniel
Approximating sparsest cut in low-treewidth graphs via combinatorial diameter
arXiv: 2111.06299 (2021)
Open Access
Bérczi, Kristóf; Mnich, Matthias; Vincze, Roland
Efficient approximations for many-visits multiple traveling salesman problems
arXiv: 2201.02054 (2021)
Open Access
Danda, Umesh Sandeep; Ramakrishna, G.; Schmidt, Jens M.; Srikanth, M.
On short fastest paths in temporal graphs
International Conference and Workshops on Algorithms and Computation (WALCOM 2021)
Publisher DOI

2020

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

2019

Göke, Alexander; Mendoza Cadena, Lydia Mirabel; Mnich, Matthias
Resolving infeasibility of linear systems: a parameterized approach
International Symposium on Parameterized and Exact Computation (IPEC 2019)
Open Access | Publisher DOI
Hermelin, Danny; Mnich, Matthias; Omlor, Simon
Single machine batch scheduling to minimize the weighted number of tardy jobs
arxiv:1911.12350 (2019)
Open Access
Knop, Dušan; Koutecký, Martin; Levin, Asaf; Mnich, Matthias; Onn, Shmuel
Multitype integer monoid optimization and applications
arXiv:1909.07326 (2019)
Open Access
Berger, André; Kozma, László; Mnich, Matthias; Vincze, Roland
A time- and space-optimal algorithm for the many-visits TSP
ACM-SIAM Symposium on Discrete Algorithms (SODA 2019)
Open Access | Publisher DOI
Bérczi, Kristóf; Berger, André; Mnich, Matthias; Vincze, Roland
Degree-bounded generalized polymatroids and approximating the metric many-visits TSP
arxiv:1911.09890 (2019)
Open Access

TU Hamburg

Institute for Algorithms and Complexity

Blohmstr. 15

21079 Hamburg

E-mail : algo@tuhh.de

Phone : +49 (40) 42878-4907