Matthias Mnich | DeepAI

DeepAI AI Chat

Featured Co-authors

Hao Sun
91 publications
Michał Pilipczuk
62 publications
Christian Schulz
62 publications
Virginia Vassilevska Williams
45 publications
Dániel Marx
44 publications
Robert Ganian
39 publications
Klaus Jansen
34 publications
Gregory Gutin
33 publications
Kristóf Bérczi
31 publications
Dušan Knop
31 publications
Rahul Savani
28 publications

∙ 08/24/2023

No Polynomial Kernels for Knapsack

This paper focuses on kernelization algorithms for the fundamental Knaps...

0 Klaus Heeger, et al. ∙

∙ 08/10/2023

Checkpoint Placement for Systematic Fault-Injection Campaigns

Shrinking hardware structures and decreasing operating voltages lead to ...

0 Christian Dietrich, et al. ∙

∙ 07/14/2023

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

One of the most studied extensions of the famous Traveling Salesperson P...

0 Max Deppert, et al. ∙

∙ 07/03/2023

Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth

Dynamic programming on various graph decompositions is one of the most f...

0 Benjamin Bergougnoux, et al. ∙

∙ 05/15/2023

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

Mixed-integer linear programming (MILP) is at the core of many advanced ...

0 Sebastian Berndt, et al. ∙

∙ 09/05/2022

Resolving Infeasibility of Linear Systems: A Parameterized Approach

Deciding feasibility of large systems of linear equations and inequaliti...

0 Kristóf Bérczi, et al. ∙

∙ 07/25/2022

A Survey on Graph Problems Parameterized Above and Below Guaranteed Values

We survey the field of algorithms and complexity for graph problems para...

0 Gregory Gutin, et al. ∙

∙ 05/25/2022

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

We study the 2-Dimensional Vector Bin Packing Problem (2VBP), a generali...

0 Ariel Kulik, et al. ∙

∙ 03/07/2022

Exponentially faster fixed-parameter algorithms for high-multiplicity scheduling

We consider so-called N-fold integer programs (IPs) of the form max{c^T ...

0 David Fischer, et al. ∙

∙ 01/06/2022

Efficient Approximations for Many-Visits Multiple Traveling Salesman Problems

A fundamental variant of the classical traveling salesman problem (TSP) ...

0 Kristóf Bérczi, et al. ∙

∙ 11/11/2021

Approximating Sparsest Cut in Low-Treewidth Graphs via Combinatorial Diameter

The fundamental sparsest cut problem takes as input a graph G together w...

0 Parinya Chalermsook, et al. ∙

∙ 07/10/2021

Hitting Weighted Even Cycles in Planar Graphs

A classical branch of graph algorithms is graph transversals, where one ...

0 Alexander Göke, et al. ∙

∙ 12/23/2020

Recent Advances in Practical Data Reduction

Over the last two decades, significant advances have been made in the de...

0 Faisal Abu-Khzam, et al. ∙

∙ 07/21/2020

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

In the Many-visits Path TSP, we are given a set of n cities along with t...

0 Kristóf Bérczi, et al. ∙

∙ 07/06/2020

Solving Packing Problems with Few Small Items Using Rainbow Matchings

An important area of combinatorial optimization is the study of packing ...

0 Max Bannach, et al. ∙

∙ 04/29/2020

Dense Steiner problems: Approximation algorithms and inapproximability

The Steiner Tree problem is a classical problem in combinatorial optimiz...

0 Marek Karpinski, et al. ∙

∙ 03/11/2020

Hitting Long Directed Cycles is Fixed-Parameter Tractable

In the Directed Long Cycle Hitting Set problem we are given a directed g...

0 Alexander Göke, et al. ∙

∙ 03/05/2020

Parameterized Algorithms for Generalizations of Directed Feedback Vertex Set

The Directed Feedback Vertex Set (DFVS) problem takes as input a directe...

0 Alexander Göke, et al. ∙

∙ 11/27/2019

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

The 1|B,r_j|∑ w_jU_j scheduling problem takes as input a batch setup tim...

0 Danny Hermelin, et al. ∙

∙ 11/22/2019

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

In the Bounded Degree Matroid Basis Problem, we are given a matroid and ...

0 Kristóf Bérczi, et al. ∙

∙ 09/16/2019

Multitype Integer Monoid Optimization and Applications

Configuration integer programs (IP) have been key in the design of algor...

0 Dušan Knop, et al. ∙

∙ 05/26/2019

Engineering Kernelization for Maximum Cut

Kernelization is a general theoretical framework for preprocessing insta...

0 Damir Ferizovic, et al. ∙

∙ 12/05/2018

Voting and Bribing in Single-Exponential Time

We introduce a general problem about bribery in voting systems. In the R...

0 Dušan Knop, et al. ∙

∙ 04/17/2018

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

The many-visits traveling salesperson problem (MV-TSP) asks for an optim...

0 Andre Berger, et al. ∙

∙ 01/29/2018

A Unifying Framework for Manipulation Problems

Manipulation models for electoral systems are a core research theme in s...

0 Dušan Knop, et al. ∙

∙ 09/26/2017

Reachability Switching Games

In this paper, we study the problem of deciding the winner of reachabili...

0 John Fearnley, et al. ∙

∙ 09/06/2017

Parameterized complexity of machine scheduling: 15 open problems

Machine scheduling problems are a long-time key domain of algorithms and...

0 Matthias Mnich, et al. ∙

∙ 07/02/2017

Dynamic Parameterized Problems and Algorithms

Fixed-parameter algorithms and kernelization are two powerful methods to...

0 Josh Alman, et al. ∙

Are you a researcher?
Expose your work
to one of the largest
A.I. communities in the world