Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints

Authors Dušan Knop , Michał Pilipczuk, Marcin Wrochna



PDF
Thumbnail PDF

File

LIPIcs.STACS.2019.44.pdf
  • Filesize: 0.75 MB
  • 15 pages

Document Identifiers

Author Details

Dušan Knop
  • Algorithmics and Computational Complexity, Faculty IV, TU Berlin, Germany
  • Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Czech Republic
Michał Pilipczuk
  • Institute of Informatics, University of Warsaw, Poland
Marcin Wrochna
  • Institute of Informatics, University of Warsaw, Poland
  • University of Oxford, UK

Cite AsGet BibTex

Dušan Knop, Michał Pilipczuk, and Marcin Wrochna. Tight Complexity Lower Bounds for Integer Linear Programming with Few Constraints. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 44:1-44:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.STACS.2019.44

Abstract

We consider the standard ILP Feasibility problem: given an integer linear program of the form {Ax = b, x >= 0}, where A is an integer matrix with k rows and l columns, x is a vector of l variables, and b is a vector of k integers, we ask whether there exists x in N^l that satisfies Ax = b. Each row of A specifies one linear constraint on x; our goal is to study the complexity of ILP Feasibility when both k, the number of constraints, and |A|_infty, the largest absolute value of an entry in A, are small. Papadimitriou [Christos H. Papadimitriou, 1981] was the first to give a fixed-parameter algorithm for ILP Feasibility under parameterization by the number of constraints that runs in time ((|A |_infty + |b|_infty) * k)^O(k^2). This was very recently improved by Eisenbrand and Weismantel [Friedrich Eisenbrand and Robert Weismantel, 2018], who used the Steinitz lemma to design an algorithm with running time (k |A|_infty)^{O(k)}* |b|_infty^2, which was subsequently improved by Jansen and Rohwedder [Klaus Jansen and Lars Rohwedder, 2019] to O(k |A |_infty)^k* log |b|_infty. 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)}* (l+|{b}|_infty)^{o(k)} would contradict the Exponential Time Hypothesis (ETH). This improves previous non-tight lower bounds of Fomin et al. [Fedor V. Fomin et al., 2018]. 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. [Martin Koutecký et al., 2018] that {ILP Feasibility} can be solved in time |A |_infty^{2^O(td_D(A))} * (k+l+log |b|_infty)^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+l)^O(1) would contradict the ETH.

Subject Classification

ACM Subject Classification
  • Theory of computation → Integer programming
  • Theory of computation → Fixed parameter tractability
Keywords
  • integer linear programming
  • fixed-parameter tractability
  • ETH

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. Amir Abboud, Karl Bringmann, Danny Hermelin, and Dvir Shabtay. SETH-based lower bounds for Subset Sum and Bicriteria Path. In SODA 2019, pages 41-57. SIAM, 2019. Google Scholar
  2. Matthias Aschenbrenner and Raymond Hemmecke. Finiteness Theorems in Stochastic Integer Programming. Foundations of Computational Mathematics, 7(2):183-227, 2007. Google Scholar
  3. Marthe Bonamy, Łukasz Kowalik, Michał Pilipczuk, Arkadiusz Socała, and Marcin Wrochna. Tight Lower Bounds for the Complexity of Multicoloring. In ESA 2017, volume 87 of LIPIcs, pages 18:1-18:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  4. Nader H. Bshouty. Optimal Algorithms for the Coin Weighing Problem with a Spring Scale. In COLT 2009, 2009. Google Scholar
  5. David G Cantor and WH Mills. Determination of a subset from certain combinatorial properties. Canad. J. Math, 18:42-48, 1966. Google Scholar
  6. Lin Chen and Dániel Marx. Covering a tree with rooted subtrees - parameterized and approximation algorithms. In SODA 2018, pages 2801-2820. SIAM, 2018. Google Scholar
  7. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, and Saket Saurabh. Parameterized Algorithms. Springer, 2015. Google Scholar
  8. Friedrich Eisenbrand, Christoph Hunkenschröder, and Kim-Manuel Klein. Faster Algorithms for Integer Programs with Block Structure. In ICALP 2018, volume 107 of LIPIcs, pages 49:1-49:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  9. Friedrich Eisenbrand and Robert Weismantel. Proximity results and faster algorithms for Integer Programming using the Steinitz Lemma. In SODA 2018, pages 808-816. SIAM, 2018. Google Scholar
  10. Fedor V. Fomin, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. On the Optimality of Pseudo-polynomial Algorithms for Integer Programming. In ESA 2018, volume 112 of LIPIcs, pages 31:1-31:13. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  11. András Frank and Éva Tardos. An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica, 7(1):49-65, 1987. Google Scholar
  12. Vladimir Grebinski and Gregory Kucherov. Optimal Reconstruction of Graphs under the Additive Model. Algorithmica, 28(1):104-124, 2000. Google Scholar
  13. Raymond Hemmecke, Shmuel Onn, and Lyubov Romanchuk. n-Fold integer programming in cubic time. Math. Program., 137(1-2):325-341, 2013. Google Scholar
  14. Russell Impagliazzo and Ramamohan Paturi. On the Complexity of k-SAT. J. Comput. Syst. Sci., 62(2):367-375, 2001. Google Scholar
  15. Russell Impagliazzo, Ramamohan Paturi, and Francis Zane. Which Problems Have Strongly Exponential Complexity? J. Comput. Syst. Sci., 63(4):512-530, 2001. Google Scholar
  16. Klaus Jansen, Kim-Manuel Klein, Marten Maack, and Malin Rau. Empowering the Configuration-IP - New PTAS Results for Scheduling with Setups Times. In ITCS 2019, volume 124 of LIPIcs, pages 44:1-44:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  17. Klaus Jansen and Lars Rohwedder. On Integer Programming and Convolution. In ITCS 2019, volume 124 of LIPIcs, pages 43:1-43:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. Google Scholar
  18. Ravi Kannan. Minkowski’s Convex Body Theorem and Integer Programming. Mathematics of Operations Research, 12(3):415-440, 1987. Google Scholar
  19. Kim-Manuel Klein. About the Complexity of Two-Stage Stochastic IPs. CoRR, abs/1901.01135, 2019. Google Scholar
  20. Dušan Knop and Martin Koutecký. Scheduling meets n-fold integer programming. J. Scheduling, 21(5):493-503, 2018. Google Scholar
  21. Dušan Knop, Martin Koutecký, and Matthias Mnich. Combinatorial n-fold Integer Programming and Applications. In ESA 2017, volume 87 of LIPIcs, pages 54:1-54:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  22. Dušan Knop, Martin Koutecký, and Matthias Mnich. Voting and Bribing in Single-Exponential Time. In STACS 2017, volume 66 of LIPIcs, pages 46:1-46:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. Google Scholar
  23. Dušan Knop, Michał Pilipczuk, and Marcin Wrochna. Tight complexity lower bounds for integer linear programming with few constraints. CoRR, abs/1811.01296, 2018. URL: http://arxiv.org/abs/1811.01296.
  24. Martin Koutecký, Asaf Levin, and Shmuel Onn. A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs. In ICALP 2018, volume 107 of LIPIcs, pages 85:1-85:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. Google Scholar
  25. Hendrik W. Lenstra. Integer Programming with a Fixed Number of Variables. Mathematics of Operations Research, 8(4):538-548, 1983. Google Scholar
  26. Bernt Lindström. On a combinatorial problem in number theory. Canad. Math. Bull, 8(4):477-490, 1965. Google Scholar
  27. Jesús A. De Loera, Raymond Hemmecke, and Matthias Köppe. Algebraic and Geometric Ideas in the Theory of Discrete Optimization, volume 14 of MOS-SIAM Series on Optimization. SIAM, 2013. Google Scholar
  28. Jaroslav Nešetřil and Patrice Ossona de Mendez. Sparsity - Graphs, Structures, and Algorithms, volume 28 of Algorithms and combinatorics. Springer, 2012. Google Scholar
  29. Christos H. Papadimitriou. On the complexity of integer programming. J. ACM, 28(4):765-768, 1981. Google Scholar
  30. Craig A. Tovey. A simplified NP-complete satisfiability problem. Discrete Applied Mathematics, 8(1):85-89, 1984. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail