2 citations · 2 across the 4 of their papers we have counts for
7 papers · 1 filter
Polynomial Kernels for Tracking Shortest Paths
Václav Blažej, Pratibha Choudhary, Dušan Knop +3
Given an undirected graph , vertices , and an integer , Tracking Shortest Paths requires deciding whether there exists a set of vertices su…
Scheduling Kernels via Configuration LP
Dušan Knop, Martin Koutecký
Makespan minimization (on parallel identical or unrelated machines) is arguably the most natural and studied scheduling problem. A common approach in practical algorithm design is…
Multitype Integer Monoid Optimization and Applications
Dušan Knop, Martin Koutecký, Asaf Levin +2
Configuration integer programs (IP) have been key in the design of algorithms for NP-hard high-multiplicity problems since the pioneering work of Gilmore and Gomory [Oper. Res., 19…
Voting and Bribing in Single-Exponential Time
Dušan Knop, Martin Koutecký, Matthias Mnich
We introduce a general problem about bribery in voting systems. In the -Multi-Bribery problem, the goal is to bribe a set of voters at minimum cost such that a desired…
Tight complexity lower bounds for integer linear programming with few constraints
Dušan Knop, Michał Pilipczuk, Marcin Wrochna
We consider the ILP Feasibility problem: given an integer linear program , where is an integer matrix with rows and columns and is a vector…
Evaluating and Tuning n-fold Integer Programming
Kateřina Altmanová, Dušan Knop, Martin Koutecký
In recent years, algorithmic breakthroughs in stringology, computational social choice, scheduling, etc., were achieved by applying the theory of so-called -fold integer program…