MKMartin Koutecký

Martin Koutecký

*This is an algorithmically generated author record based on publicly available information.

Current Organizations / Institutes

The organizations/institutes from the scholar's latest article

Previous Organizations / Institutes

The organizations / institutes from the scholar's other articles in the past ten years


Martin Koutecký has a total of 64 co-authors. Here are the top co-authors by number of shared publications:


Latest Publications

  • Open Access

    Tight lower bounds for block-structured integer programs

    by Christoph Hunkenschröder, Kim-Manuel Klein, Martin Koutecký, Alexandra Lassota, Asaf Levin

    We study fundamental block-structured integer programs called tree-fold and multi-stage IPs. Tree-fold IPs have a constraint matrix with independent blocks linked together by few constraints in a recursive pattern. Transposing this constraint matrix yields the constraint matrix of multi-stage IPs. The state-of-the-art algorithms to solve these IPs have an exponential gap in their running times, making it natural to ask whether this gap is inherent. We answer this question in the affirmative. Assuming the Exponential Time Hypothesis, we prove lower bounds showing that the exponential difference is necessary. This also proves that the known algorithms are essentially optimal. Moreover, we prove unconditional lower bounds on the size of the Graver basis elements, a fundamental building block of all known algorithms to solve these IPs. This shows that none of the current approaches can be improved beyond this bound unconditionally.


  • Sparse Integer Programming Is Fixed-Parameter Tractable

    by Friedrich Eisenbrand, Christoph Hunkenschröder, Kim-Manuel Klein, Martin Koutecký, Asaf Levin, Shmuel Onn

    We study the general integer programming problem where the number of variables n is a variable part of the input. We consider two natural parameters of the constraint matrix A: its numeric measure a and its sparsity measure d. We present an algorithm for solving integer programming in time [ ], where g is some computable function of the parameters a and d, and L is the binary encoding length of the input. In particular, integer programming is fixed-parameter tractable parameterized by a and d, and is solvable in polynomial time for every fixed a and d. Our results also extend to nonlinear separable convex objective functions. Funding: F. Eisenbrand, C. Hunkenschröder, and K.-M. Klein were supported by the Swiss National Science Foundation (SNSF) within the project “Convexity, geometry of numbers, and the complexity of integer programming” [Grant 163071]. A. Levin and S. Onn are partially supported by the Israel Science Foundation [Grant 308/18]. A. Levin is also partially supported by the Israel Science Foundation [Grant 1467/22]. S. Onn is also partially supported by the Dresner Chair at the Technion. M. Koutecký is partially supported by Charles University project UNCE 24/SCI/008, and by the project 22-22997S of the Grantová Agentura České Republiky (GA ČR).


  • Open Access

    Parameterized algorithms for block-structured integer programs with large entries

    by Jana Cslovjecsek, Martin Koutecký, Alexandra Lassota, Michał Pilipczuk, Adam Polak

    We study two classic variants of block-structured integer programming. Two-stage stochastic programs are integer programs of the form $\{A_i \mathbf{x} + D_i \mathbf{y}_i = \mathbf{b}_i\textrm{ for all }i=1,\ldots,n\}$, where $A_i$ and $D_i$ are bounded-size matrices. On the other hand, $n$-fold programs are integer programs of the form $\{{\sum_{i=1}^n C_i\mathbf{y}_i=\mathbf{a}} \textrm{ and } D_i\mathbf{y}_i=\mathbf{b}_i\textrm{ for all }i=1,\ldots,n\}$, where again $C_i$ and $D_i$ are bounded-size matrices. It is known that solving these kind of programs is fixed-parameter tractable when parameterized by the maximum dimension among the relevant matrices $A_i,C_i,D_i$ and the maximum absolute value of any entry appearing in the constraint matrix. We show that the parameterized tractability results for two-stage stochastic and $n$-fold programs persist even when one allows large entries in the global part of the program. More precisely, we prove that: - The feasibility problem for two-stage stochastic programs is fixed-parameter tractable when parameterized by the dimensions of matrices $A_i,D_i$ and by the maximum absolute value of the entries of matrices $D_i$. That is, we allow matrices $A_i$ to have arbitrarily large entries. - The linear optimization problem for $n$-fold integer programs that are uniform -- all matrices $C_i$ are equal -- is fixed-parameter tractable when parameterized by the dimensions of matrices $C_i$ and $D_i$ and by the maximum absolute value of the entries of matrices $D_i$. That is, we require that $C_i=C$ for all $i=1,\ldots,n$, but we allow $C$ to have arbitrarily large entries. In the second result, the uniformity assumption is necessary; otherwise the problem is $\mathsf{NP}$-hard already when the parameters take constant values. Both our algorithms are weakly polynomial: the running time is measured in the total bitsize of the input.49 pages. This is the TheoretiCS journal version


  • (Near)-Optimal Algorithms for Sparse Separable Convex Integer Programs

    by Christoph Hunkenschröder, Martin Koutecký, Asaf Levin, Tung Anh Vu

  • Open Access

    (Near)-Optimal Algorithms for Sparse Separable Convex Integer Programs

    by Christoph Hunkenschröder, Martin Koutecký, Asaf Levin, Tung Anh Vu

    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} = \mathbf{b}, \, \mathbf{l} \leq \mathbf{x} \leq \mathbf{u}, \, \mathbf{x} \in \mathbb{Z}^n\}$. The number of variables $n$ is a variable part of the input, and we consider the regime where the constraint matrix $A$ has small coefficients $\|A\|_\infty$ and small primal or dual treedepth $\mathrm{td}_P(A)$ or $\mathrm{td}_D(A)$, respectively. Equivalently, we consider block-structured matrices, in particular $n$-fold, tree-fold, $2$-stage and multi-stage matrices. We ask about the possibility of near-linear time algorithms in the general case of (non-linear) separable convex functions. The techniques of previous works for the linear case are inherently limited to it; in fact, no strongly-polynomial algorithm may exist due to a simple unconditional information-theoretic lower bound of $n \log \|\mathbf{u}-\mathbf{l}\|_\infty$, where $\mathbf{l}, \mathbf{u}$ are the vectors of lower and upper bounds. Our first result is that with parameters $\mathrm{td}_P(A)$ and $\|A\|_\infty$, this lower bound can be matched (up to dependency on the parameters). Second, with parameters $\mathrm{td}_D(A)$ and $\|A\|_\infty$, the situation is more involved, and we design an algorithm with time complexity $g(\mathrm{td}_D(A), \|A\|_\infty) n \log n \log \|\mathbf{u}-\mathbf{l}\|_\infty$ where $g$ is some computable function. We conjecture that a stronger lower bound is possible in this regime, and our algorithm is in fact optimal. Our algorithms combine ideas from scaling, proximity, and sensitivity of integer programs, together with a new dynamic data structure.

  • Open Access

    Complexity of scheduling few types of jobs on related and unrelated machines

    by Martin Koutecký, Johannes Zink

    The task of scheduling jobs to machines while minimizing the total makespan, the sum of weighted completion times, or a norm of the load vector are among the oldest and most fundamental tasks in combinatorial optimization. Since all of these problems are in general -hard, much attention has been given to the regime where there is only a small number k of job types, but possibly the number of jobs n is large; this is the few job types, high-multiplicity regime. Despite many positive results, the hardness boundary of this regime was not understood until now. We show that makespan minimization on uniformly related machines ( $$Q|HM|C_{\max }$$ Q | H M | C max ) is -hard already with 6 job types, and that the related Cutting Stock problem is -hard already with 8 item types. For the more general unrelated machines model ( $$R|HM|C_{\max }$$ R | H M | C max ), we show that if the largest job size $$p_{\max }$$ p max or the number of jobs n is polynomially bounded in the instance size |I|, there are algorithms with complexity $$|I|^{{{\,\mathrm{\textrm{poly}}\,}}(k)}$$ | I | poly ( k ) . Our main result is that this is unlikely to be improved because $$Q||C_{\max }$$ Q | | C max is $$\mathsf {W[1]}$$ W [ 1 ] -hard parameterized by k already when n, $$p_{\max }$$ p max , and the numbers describing the machine speeds are polynomial in |I|; the same holds for $$R||C_{\max }$$ R | | C max (without machine speeds) when the job sizes matrix has rank 2. Our positive and negative results also extend to the objectives $$\ell _2$$ ℓ 2 -norm minimization of the load vector and, partially, sum of weighted completion times $$\sum w_j C_j$$ ∑ w j C j . Along the way, we answer affirmatively the question whether makespan minimization on identical machines ( $$P||C_{\max }$$ P | | C max ) is fixed-parameter tractable parameterized by k, extending our understanding of this fundamental problem. Together with our hardness results for $$Q||C_{\max }$$ Q | | C max , this implies that the complexity of $$P|HM|C_{\max }$$ P | H M | C max is the only remaining open case.


  • Tight Lower Bounds for Block-Structured Integer Programs

    by Christoph Hunkenschröder, Kim-Manuel Klein, Martin Koutecký, Alexandra Lassota, Asaf Levin


  • Correction to: A Polyhedral Perspective on Tropical Convolutions

    by Cornelius Brand, Martin Koutecký, Alexandra Lassota

  • Open Access

    Tight Lower Bounds for Block-Structured Integer Programs

    by Christoph Hunkenschröder, Kim-Manuel Klein, Martin Koutecký, Alexandra Lassota, Asaf Levin

    We study fundamental block-structured integer programs called tree-fold and multi-stage IPs. Tree-fold IPs admit a constraint matrix with independent blocks linked together by few constraints in a recursive pattern; and transposing their constraint matrix yields multi-stage IPs. The state-of-the-art algorithms to solve these IPs have an exponential gap in their running times, making it natural to ask whether this gap is inherent. We answer this question affirmative. Assuming the Exponential Time Hypothesis, we prove lower bounds showing that the exponential difference is necessary, and that the known algorithms are near optimal. Moreover, we prove unconditional lower bounds on the norms of the Graver basis, a fundamental building block of all known algorithms to solve these IPs. This shows that none of the current approaches can be improved beyond this bound.

  • Open Access

    Characterization of matrices with bounded Graver bases and depth parameters and applications to integer programming

    by Marcin Briański, Martin Koutecký, Daniel Král’, Kristýna Pekárková, Felix Schröder

    An intensive line of research on fixed parameter tractability of integer programming is focused on exploiting the relation between the sparsity of a constraint matrix A and the norm of the elements of its Graver basis. In particular, integer programming is fixed parameter tractable when parameterized by the primal tree-depth and the entry complexity of A, and when parameterized by the dual tree-depth and the entry complexity of A; both these parameterization imply that A is sparse, in particular, the number of its non-zero entries is linear in the number of columns or rows, respectively. We study preconditioners transforming a given matrix to a row-equivalent sparse matrix if it exists and provide structural results characterizing the existence of a sparse row-equivalent matrix in terms of the structural properties of the associated column matroid. In particular, our results imply that the $$\ell _1$$ ℓ 1 -norm of the Graver basis is bounded by a function of the maximum $$\ell _1$$ ℓ 1 -norm of a circuit of A. We use our results to design a parameterized algorithm that constructs a matrix row-equivalent to an input matrix A that has small primal/dual tree-depth and entry complexity if such a row-equivalent matrix exists. Our results yield parameterized algorithms for integer programming when parameterized by the $$\ell _1$$ ℓ 1 -norm of the Graver basis of the constraint matrix, when parameterized by the $$\ell _1$$ ℓ 1 -norm of the circuits of the constraint matrix, when parameterized by the smallest primal tree-depth and entry complexity of a matrix row-equivalent to the constraint matrix, and when parameterized by the smallest dual tree-depth and entry complexity of a matrix row-equivalent to the constraint matrix.