Dušan Knop

Dr. Dušan Knop

orcid

Research Focus & Metrics

Academic Career Length

12Years (2015-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
15 November 2017 in Journal of Scheduling
Verified
Journal Article
Closed access
PDF file
DKDušan Knop
Dušan Knop
MKMartin Koutecký
Martin Koutecký

1 June 2020 in ACM Transactions on Computation Theory
Verified
Journal Article
Open access
DKDušan Knop
Dušan Knop
MPMichał Pilipczuk
Michał Pilipczuk
MWMarcin Wrochna
Marcin Wrochna
We consider the standard ILP F easibility problem: given an integer linear program of the form {A x = b, x ⩾ 0}, where A is an integer matrix with k rows and ℓ columns, x is a vector of ℓ variables, and b is a vector of k integers, we ask whether there exists x ∈ N ℓ that satisfies Ax = b. Each row of A specifies one linear constraint on x; our goal is to study the complexity of ILP F easibility when both k , the number of constraints, and ‖A‖ ∞ , the largest absolute value of an entry in A , are small. Papadimitriou was the first to give a fixed-parameter algorithm for ILP F easibility under parameterization by the number of constraints that runs in time ((‖A‖ ∞ + ‖b‖ ∞ ) ⋅ k ) O ( k 2 ) . This was very recently improved by Eisenbrand and Weismantel, who used the Steinitz lemma to design an algorithm with running time ( k ‖A‖ ∞ ) O ( k ) ⋅ log ‖b‖ ∞ , which was subsequently refined by Jansen and Rohwedder to O (√ k ‖A‖ ∞ ) k ⋅ log (‖ A‖ ∞ + ‖b‖ ∞ ) ⋅ log ‖A‖ ∞ . We prove that for {0, 1}-matrices A , the running time of the algorithm of Eisenbrand and Weismantel is probably optimal: an algorithm with running time 2 o ( k log k ) ⋅ (ℓ + ‖b‖ ∞ ) o ( k ) would contradict the exponential time hypothesis. This improves previous non-tight lower bounds of Fomin et al. We then consider integer linear programs that may have many constraints, but they need to be structured in a “shallow” way. Precisely, we consider the parameter dual treedepth of the matrix A , denoted td D ( A ), which is the treedepth of the graph over the rows of A , where two rows are adjacent if in some column they simultaneously contain a non-zero entry. It was recently shown by Koutecký et al. that ILP F easibility can be solved in time ‖A‖ ∞ 2 O (td D ( A )) ⋅ ( k + ℓ + log ‖b‖ ∞ ) O (1) . We present a streamlined proof of this fact and prove that, again, this running time is probably optimal: even assuming that all entries of A and b are in {−1, 0, 1}, the existence of an algorithm with running time 2 2 o (td D ( A )) ⋅ ( k + ℓ) O (1) would contradict the exponential time hypothesis.

20 November 2019 in Mathematical Programming
Verified
Journal Article
Open access
PDF file
DKDušan Knop
Dušan Knop
MKMartin Koutecký
Martin Koutecký
MMMatthias Mnich
Matthias Mnich
Many fundamental \(\mathsf {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 of the program, and polynomial in the size of the ILP. That algorithm became a ubiquitous tool in the design of fixed-parameter algorithms for \(\mathsf {NP}\)-hard problems, where one wishes to isolate the hardness of a problem by some parameter. However, in many cases using Lenstra’s algorithm has two drawbacks: First, the run time of the resulting algorithms is often double-exponential in the parameter, and second, an ILP formulation in small dimension cannot easily express problems involving many different costs. Inspired by the work of Hemmecke et al. (Math Program 137(1–2, Ser. A):325–341, 2013 ), we develop a single-exponential algorithm for so-called combinatorialn-fold integer programs, which are remarkably similar to prior ILP formulations for various problems, but unlike them, also allow variable dimension. We then apply our algorithm to many relevant problems problems like Closest String, Swap Bribery, Weighted Set Multicover, and several others, and obtain exponential speedups in the dependence on the respective parameters, the input size, or both. Unlike Lenstra’s algorithm, which is essentially a bounded search tree algorithm, our result uses the technique of augmenting steps. At its heart is a deep result stating that in combinatorial n-fold IPs, existence of an augmenting step implies existence of a “local” augmenting step, which can be found using dynamic programming. Our results provide an important insight into many problems by showing that they exhibit this phenomenon, and highlights the importance of augmentation techniques.

22 June 2020 in ACM Transactions on Economics and Computation
Verified
Journal Article
Open access
DKDušan Knop
Dušan Knop
MKMartin Koutecký
Martin Koutecký
MMMatthias Mnich
Matthias Mnich
We introduce a general problem about bribery in voting systems. In the R -M ulti -B ribery problem, the goal is to bribe a set of voters at minimum cost such that a desired candidate is a winner in the perturbed election under the voting rule R . Voters assign prices for withdrawing their vote, for swapping the positions of two consecutive candidates in their preference order, and for perturbing their approval count to favour candidates. As our main result, we show that R -M ulti -B ribery is fixed-parameter tractable parameterized by the number of candidates | C | with only a single-exponential dependence on | C |, for many natural voting rules R , including all natural scoring protocols, maximin rule, Bucklin rule, Fallback rule, SP-AV, and any C1 rule. The vast majority of previous work done in the setting of few candidates proceeds by grouping voters into at most | C |! types by their preference, constructing an integer linear program with | C |! 2 variables, and solving it by Lenstra’s algorithm in time | C |! | C |! 2 , hence double-exponential in | C |. Note that it is not possible to encode a large number of different voter costs in this way and still obtain a fixed-parameter algorithm, as that would increase the number of voter types and hence the dimension. These two obstacles of double-exponential complexity and restricted costs have been formulated as “Challenges #1 and #2” of the “Nine Research Challenges in Computational Social Choice” by Bredereck et al. Hence, our result resolves the parameterized complexity of R -S wap -B ribery for the aforementioned voting rules plus Kemeny’s rule, and for all rules except Kemeny brings the dependence on | C | down to single-exponential. The engine behind our progress is the use of a new integer linear programming formulation, using so-called “ n -fold integer programming.” Since its format is quite rigid, we introduce “extended n -fold IP,” which allows many useful modeling tricks. Then, we model R -M ulti -B ribery as an extended n -fold IP and apply an algorithm of Hemmecke et al. [Math. Prog. 2013].

1 August 2017
Verified
Conference Paper
Closed access
PDPavel Dvořák
Pavel Dvořák
EEEduard Eiben
Eduard Eiben
RGRobert Ganian
Robert Ganian
DKDušan Knop
Dušan Knop
SOSebastian Ordyniak
Sebastian Ordyniak
Integer Linear Programming (ILP) has a broad range of applications in various areas of artificial intelligence. Yet in spite of recent advances, we still lack a thorough understanding of which structural restrictions make ILP tractable. Here we study ILP instances consisting of a small number of ``global'' variables and/or constraints such that the remaining part of the instance consists of small and otherwise independent components; this is captured in terms of a structural measure we call fracture backdoors which generalizes, for instance, the well-studied class of N-fold ILP instances. Our main contributions can be divided into three parts. First, we formally develop fracture backdoors and obtain exact and approximation algorithms for computing these. Second, we exploit these backdoors to develop several new parameterized algorithms for ILP; the performance of these algorithms will naturally scale based on the number of global variables or constraints in the instance. Finally, we complement the developed algorithms with matching lower bounds. Altogether, our results paint a near-complete complexity landscape of ILP with respect to fracture backdoors.

1 November 2021 in Artificial Intelligence
Verified
Journal Article
Open access
PDPavel Dvořák
Pavel Dvořák
EEEduard Eiben
Eduard Eiben
RGRobert Ganian
Robert Ganian
DKDušan Knop
Dušan Knop
SOSebastian Ordyniak
Sebastian Ordyniak