Document Open Access Logo

A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs

Authors Martin Koutecký , Asaf Levin, Shmuel Onn

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.85.pdf
  • Filesize: 0.57 MB
  • 14 pages

Document Identifiers

Author Details

Martin Koutecký
  • Technion - Israel Institute of Technology, Haifa, Israel, and , Charles University, Prague, Czech Republic
Asaf Levin
  • Technion - Israel Institute of Technology, Haifa, Israel
Shmuel Onn
  • Technion - Israel Institute of Technology, Haifa, Israel

Funding

  • Koutecký, Martin: Supported by a Technion postdoctoral fellowship and the project 17-09142S of GA ČR.
  • Levin, Asaf: Supported by a grant from the GIF, the German-Israeli Foundation for Scientific Research and Development (grant number I-1366-407.6/2016).
  • Onn, Shmuel: Supported by the Dresner chair.

Cite As Get BibTex

Martin Koutecký, Asaf Levin, and Shmuel Onn. A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 85:1-85:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.ICALP.2018.85

Abstract

The theory of n-fold integer programming has been recently emerging as an important tool in parameterized complexity. The input to an n-fold integer program (IP) consists of parameter A, dimension n, and numerical data of binary encoding length L. It was known for some time that such programs can be solved in polynomial time using O(n^{g(A)}L) arithmetic operations where g is an exponential function of the parameter. In 2013 it was shown that it can be solved in fixed-parameter tractable time using O(f(A)n^3L) arithmetic operations for a single-exponential function f. This, and a faster algorithm for a special case of combinatorial n-fold IP, have led to several very recent breakthroughs in the parameterized complexity of scheduling, stringology, and computational social choice. In 2015 it was shown that it can be solved in strongly polynomial time using O(n^{g(A)}) arithmetic operations.
Here we establish a result which subsumes all three of the above results by showing that n-fold IP can be solved in strongly polynomial fixed-parameter tractable time using O(f(A)n^6 log n) arithmetic operations. In fact, our results are much more general, briefly outlined as follows.
- There is a strongly polynomial algorithm for integer linear programming (ILP) whenever a so-called Graver-best oracle is realizable for it.
- Graver-best oracles for the large classes of multi-stage stochastic and tree-fold ILPs can be realized in fixed-parameter tractable time. Together with the previous oracle algorithm, this newly shows two large classes of ILP to be strongly polynomial; in contrast, only few classes of ILP were previously known to be strongly polynomial.
- We show that ILP is fixed-parameter tractable parameterized by the largest coefficient |A |_infty and the primal or dual treedepth of A, and that this parameterization cannot be relaxed, signifying substantial progress in understanding the parameterized complexity of ILP.

Subject Classification

ACM Subject Classification
  • Theory of computation → Fixed parameter tractability
Keywords
  • integer programming
  • parameterized complexity
  • Graver basis
  • n-fold integer programming

Metrics

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

Related Versions

References

  1. Gautam Appa, Balázs Kotnyek, Konstantinos Papalamprou, and Leonidas Pitsoulis. Optimization with binet matrices. Operations research letters, 35(3):345-352, 2007. Google Scholar
  2. Stephan Artmann, Robert Weismantel, and Rico Zenklusen. A strongly polynomial algorithm for bimodular integer linear programming. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, pages 1206-1219. ACM, 2017. Google Scholar
  3. Matthias Aschenbrenner and Raymond Hemmecke. Finiteness theorems in stochastic integer programming. Foundations of Computational Mathematics, 7(2):183-227, 2007. Google Scholar
  4. Lin Chen and Dániel Marx. Covering a tree with rooted subtrees-parameterized and approximation algorithms. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, pages 2801-2820. SIAM, 2018. Google Scholar
  5. 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
  6. Jesús A. De Loera, Raymond Hemmecke, and Jon Lee. On augmentation algorithms for linear and integer-linear programming: From Edmonds-Karp to Bland and beyond. SIAM Journal on Optimization, 25(4):2494-2511, 2015. Google Scholar
  7. Pavel Dvořák, Eduard Eiben, Robert Ganian, Dušan Knop, and Sebastian Ordyniak. Solving integer linear programs with a small number of global variables and constraints. arXiv preprint arXiv:1706.06084, 2017. Google Scholar
  8. András Frank and Éva Tardos. An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica, 7(1):49-65, 1987. Google Scholar
  9. Eugene C. Freuder. Complexity of K-tree structured constraint satisfaction problems. In Proceedings of the 8th National Conference on Artificial Intelligence, pages 4-9, 1990. Google Scholar
  10. Robert Ganian and Sebastian Ordyniak. The complexity landscape of decompositional parameters for ILP. Artificial Intelligence, 2018. Google Scholar
  11. Robert Ganian, Sebastian Ordyniak, and M. S. Ramanujan. Going beyond primal treewidth for (M)ILP. In Satinder P. Singh and Shaul Markovitch, editors, AAAI, pages 815-821. AAAI Press, 2017. Google Scholar
  12. Raymond Hemmecke, Matthias Köppe, and Robert Weismantel. Graver basis and proximity techniques for block-structured separable convex integer minimization problems. Mathematical Programming, 145(1-2, Ser. A):1-18, 2014. Google Scholar
  13. Raymond Hemmecke, Shmuel Onn, and Lyubov Romanchuk. N-fold integer programming in cubic time. Mathematical Programming, pages 1-17, 2013. Google Scholar
  14. Dorit S. Hochbaum and J. George Shanthikumar. Convex separable optimization is not much harder than linear optimization. Journal of the ACM, 37(4):843-862, 1990. Google Scholar
  15. Bart M. P. Jansen and Stefan Kratsch. A structural approach to kernels for ILPs: Treewidth and total unimodularity. In Nikhil Bansal and Irene Finocchi, editors, ESA, volume 9294 of Lecture Notes in Computer Science, pages 779-791. Springer, 2015. 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. arXiv preprint arXiv:1801.06460, 2018. Google Scholar
  17. Ravi Kannan. Minkowski’s convex body theorem and integer programming. Mathematics of Operations Research, 12(3):415–440, 1987. Google Scholar
  18. Dušan Knop, Martin Koutecký, and Matthias Mnich. Combinatorial n-fold integer programming and applications. In ESA, volume 87 of LIPIcs, pages 54:1-54:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. Extended version available at https://arxiv.org/abs/1705.08657. Google Scholar
  19. Dušan Knop, Martin Koutecký, and Matthias Mnich. Voting and bribing in single-exponential time. In STACS, volume 66 of LIPIcs, pages 46:1-46:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  20. Hendrik W. Lenstra, Jr. Integer programming with a fixed number of variables. Mathematics of Operations Research, 8(4):538-548, 1983. Google Scholar
  21. Shmuel Onn. Nonlinear discrete optimization. Zurich Lectures in Advanced Mathematics, European Mathematical Society, 2010. http://ie.technion.ac.il/∼onn/Book/NDO.pdf. Google Scholar
  22. Felix Reidl, Peter Rossmanith, Fernando Sánchez Villaamil, and Somnath Sikdar. A faster parameterized algorithm for treedepth. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors, ICALP (1), volume 8572 of Lecture Notes in Computer Science, pages 931-942. Springer, 2014. Google Scholar
  23. Alexander Shrijver. Theory of linear and integer programming. Interscience Series in Discrete Mathematics and Optimization. Wiley, 1986. Google Scholar
  24. Éva Tardos. A strongly polynomial algorithm to solve combinatorial linear programs. Operations Research, 34(2):250-256, 1986. Google Scholar
  25. Sergey I. Veselov and Aleksandr J. Chirkov. Integer program with bimodular matrix. Discrete Optimization, 6(2):220-222, 2009. 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact