research
∙
08/24/2023
No Polynomial Kernels for Knapsack
This paper focuses on kernelization algorithms for the fundamental Knaps...
share
research
∙
08/10/2023
Checkpoint Placement for Systematic Fault-Injection Campaigns
Shrinking hardware structures and decreasing operating voltages lead to ...
research
∙
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...
research
∙
07/03/2023
Space-Efficient Parameterized Algorithms on Graphs of Low Shrubdepth
Dynamic programming on various graph decompositions is one of the most f...
research
∙
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 ...
research
∙
09/05/2022
Resolving Infeasibility of Linear Systems: A Parameterized Approach
Deciding feasibility of large systems of linear equations and inequaliti...
research
∙
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...
research
∙
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...
research
∙
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 ...
research
∙
01/06/2022
Efficient Approximations for Many-Visits Multiple Traveling Salesman Problems
A fundamental variant of the classical traveling salesman problem (TSP) ...
research
∙
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...
research
∙
07/10/2021
Hitting Weighted Even Cycles in Planar Graphs
A classical branch of graph algorithms is graph transversals, where one ...
research
∙
12/23/2020
Recent Advances in Practical Data Reduction
Over the last two decades, significant advances have been made in the de...
research
∙
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...
research
∙
07/06/2020
Solving Packing Problems with Few Small Items Using Rainbow Matchings
An important area of combinatorial optimization is the study of packing ...
research
∙
04/29/2020
Dense Steiner problems: Approximation algorithms and inapproximability
The Steiner Tree problem is a classical problem in combinatorial optimiz...
research
∙
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...
research
∙
03/05/2020
Parameterized Algorithms for Generalizations of Directed Feedback Vertex Set
The Directed Feedback Vertex Set (DFVS) problem takes as input a directe...
research
∙
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...
research
∙
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 ...
research
∙
09/16/2019
Multitype Integer Monoid Optimization and Applications
Configuration integer programs (IP) have been key in the design of algor...
research
∙
05/26/2019
Engineering Kernelization for Maximum Cut
Kernelization is a general theoretical framework for preprocessing insta...
research
∙
12/05/2018
Voting and Bribing in Single-Exponential Time
We introduce a general problem about bribery in voting systems. In the R...
research
∙
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...
research
∙
01/29/2018
A Unifying Framework for Manipulation Problems
Manipulation models for electoral systems are a core research theme in s...
research
∙
09/26/2017
Reachability Switching Games
In this paper, we study the problem of deciding the winner of reachabili...
research
∙
09/06/2017
Parameterized complexity of machine scheduling: 15 open problems
Machine scheduling problems are a long-time key domain of algorithms and...
research
∙
07/02/2017
