49 citations · 185 across the 18 of their papers we have counts for
10 papers · 1 filter
(Near)-Optimal Algorithms for Sparse Separable Convex Integer Programs
Christoph Hunkenschröder, Martin Koutecký, Asaf Levin +1
We study the general integer programming (IP) problem of optimizing a separable convex function over the integer points of a polytope: $\min \{f(\mathbf{x}) \mid A\mathbf{x} = \mat…
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…
Matrices of optimal tree-depth and a row-invariant parameterized algorithm for integer programming
Timothy F. N. Chan, Jacob W. Cooper, Martin Koutecky +2
A long line of research on fixed parameter tractability of integer programming culminated with showing that integer programs with n variables and a constraint matrix with dual tree…
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…
A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs
Martin Koutecký, Asaf Levin, Shmuel Onn
The theory of -fold integer programming has been recently emerging as an important tool in parameterized complexity. The input to an -fold integer program (IP) consists of pa…
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…
Integer Programming in Parameterized Complexity: Three Miniatures
Tomáš Gavenčiak, Dušan Knop, Martin Koutecký
Powerful results from the theory of integer programming have recently led to substantial advances in parameterized complexity. However, our perception is that, except for Lenstra's…
Combinatorial n-fold Integer Programming and Applications
Dušan Knop, Martin Koutecký, Matthias Mnich
Many fundamental NP-hard problems can be formulated as integer linear programs (ILPs). A famous algorithm by Lenstra solves ILPs in time that is exponential only in the dimension o…
Scheduling meets n-fold Integer Programming
Dušan Knop, Martin Koutecký
Scheduling problems are fundamental in combinatorial optimization. Much work has been done on approximation algorithms for NP-hard cases, but relatively little is known about exact…
Extension Complexity, MSO Logic, and Treewidth
Petr Kolman, Martin Koutecký, Hans Raj Tiwary
We consider the convex hull of all satisfying assignments of a given MSO formula on a given graph . We show that there exists an extended formulation of the polytop…