66 citations · 154 across the 32 of their papers we have counts for
49 papers
Checkpoint Placement for Systematic Fault-Injection Campaigns
Christian Dietrich, Tim-Marek Thomas, Matthias Mnich
Shrinking hardware structures and decreasing operating voltages lead to an increasing number of transient hardware faults,which thus become a core problem to consider for safety-cr…
No Polynomial Kernels for Knapsack
Klaus Heeger, Danny Hermelin, Matthias Mnich +1
This paper focuses on kernelization algorithms for the fundamental Knapsack problem. A kernelization algorithm (or kernel) is a polynomial-time reduction from a problem onto itself…
A -Approximation for Multiple TSP with a Variable Number of Depots
Max Deppert, Matthias Kaul, Matthias Mnich
One of the most studied extensions of the famous Traveling Salesperson Problem (TSP) is the {\sc Multiple TSP}: a set of salespersons collectively traverses a set of …
Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
Benjamin Bergougnoux, Vera Chekan, Robert Ganian +5
Dynamic programming on various graph decompositions is one of the most fundamental techniques used in parameterized complexity. Unfortunately, even if we consider concepts as simpl…
New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines
Sebastian Berndt, Hauke Brinkop, Klaus Jansen +2
Mixed-integer linear programming (MILP) is at the core of many advanced algorithms for solving fundamental problems in combinatorial optimization. The complexity of solving MILPs d…
Resolving Infeasibility of Linear Systems: A Parameterized Approach
Kristóf Bérczi, Alexander Göke, Lydia Mirabel Mendoza-Cadena +1
Deciding feasibility of large systems of linear equations and inequalities is one of the most fundamental algorithmic tasks. However, due to data inaccuracies or modeling errors, i…