Document Open Access Logo

Combinatorial n-fold Integer Programming and Applications

Authors Dusan Knop, Martin Koutecky, Matthias Mnich

PDF
Thumbnail PDF

File

LIPIcs.ESA.2017.54.pdf
  • Filesize: 0.69 MB
  • 14 pages

Document Identifiers

Author Details

Dusan Knop
Martin Koutecky
Matthias Mnich

Cite As Get BibTex

Dusan Knop, Martin Koutecky, and Matthias Mnich. Combinatorial n-fold Integer Programming and Applications. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 54:1-54:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.ESA.2017.54

Abstract

Many fundamental NP-hard problems can be formulated as integer linear programs (ILPs). A famous algorithm by Lenstra allows to solve ILPs in time that is exponential only in the dimension of the program. That algorithm therefore became a ubiquitous tool in the design of fixed-parameter algorithms for NP-hard problems, where one wishes to isolate the hardness of a problem by some parameter. However, it was discovered that in many cases using Lenstra’s algorithm has two drawbacks: First, the run time of the resulting algorithms is often doubly-exponential in the parameter, and second, an ILP formulation in small dimension can not easily express problems which involve many different costs.

Inspired by the work of Hemmecke, Onn and Romanchuk [Math. Prog. 2013], we develop a single-exponential algorithm for so-called combinatorial n-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 a few representative problems like Closest String, Swap Bribery, Weighted Set Multicover, 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 an existence of an augmenting step implies an 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.

Subject Classification

Keywords
  • integer programming
  • closest strings
  • fixed-parameter algorithms

Metrics

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

References

  1. Amihood Amir, Gad M. Landau, Joong Chae Na, Heejin Park, Kunsoo Park, and Jeong Seop Sim. Efficient algorithms for consensus string problems minimizing both distance sum and radius. Theoret. Comput. Sci., 412(39):5239-5246, 2011. Google Scholar
  2. Liliana Félix Avila, Alina Garcıa, Marıa José Serna, and Dimitrios M Thilikos. A list of parameterized problems in bioinformatics. Technical report, Technical University of Catalonia, 2006. Technical report LSI-06-24-R. Google Scholar
  3. Christina Boucher and Kathleen Wilkie. Why large closest string instances are easy to solve in practice. In Proc. SPIRE 2010, volume 6393 of Lecture Notes Comput. Sci., pages 106-117, 2010. Google Scholar
  4. Robert Bredereck, Jiehua Chen, Piotr Faliszewski, Jiong Guo, Rolf Niedermeier, and Gerhard J. Woeginger. Parameterized algorithmics for computational social choice: Nine research challenges. Tsinghua Sci. Tech., 19(4):358-373, 2014. Google Scholar
  5. Robert Bredereck, Piotr Faliszewski, Rolf Niedermeier, Piotr Skowron, and Nimrod Talmon. Elections with few candidates: Prices, weights, and covering problems. In Proc. ADT 2015, volume 9346 of Lecture Notes Comput. Sci., pages 414-431, 2015. Google Scholar
  6. Laurent Bulteau, Falk Hüffner, Christian Komusiewicz, and Rolf Niedermeier. Multivariate algorithmics for NP-hard string problems. Bulletin of the EATCS, 114, 2014. Google Scholar
  7. Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, and Saket Saurabh. Parameterized algorithms. Springer, 2015. Google Scholar
  8. Daniel Dadush, Chris Peikert, and Santosh Vempala. Enumerative lattice algorithms in any norm via M-ellipsoid coverings. In Proc. FOCS 2011, pages 580-589. 2011. Google Scholar
  9. Britta Dorn and Ildikó Schlotter. Multivariate complexity analysis of swap bribery. Algorithmica, 64(1):126-151, 2012. Google Scholar
  10. Michael R. Fellows, Daniel Lokshtanov, Neeldhara Misra, Frances A. Rosamond, and Saket Saurabh. Graph layout problems parameterized by vertex cover. In Proc. ISAAC 2008, volume 5369 of Lecture Notes Comput. Sci., pages 294-305. Springer, Berlin, 2008. Google Scholar
  11. Jiří Fiala, Tomáš Gavenčiak, Dušan Knop, Martin Koutecký, and Jan Kratochvíl. Parameterized complexity of distance labeling and uniform channel assignment problems. Discrete Appl. Math., 2017. to appear. Google Scholar
  12. M. Frances and A. Litman. On covering problems of codes. Theory Comput. Syst., 30(2):113-119, 1997. Google Scholar
  13. Jakub Gajarský, Michael Lampis, and Sebastian Ordyniak. Parameterized algorithms for modular-width. In Proc. IPEC 2013, volume 8246 of Lecture Notes Comput. Sci., pages 163-176. 2013. Google Scholar
  14. Robert Ganian and Sebastian Ordyniak. The complexity landscape of decompositional parameters for ILP. In Proc. AAAI 2016, pages 710-716, 2016. Google Scholar
  15. Robert Ganian, Sebastian Ordyniak, and M. S. Ramanujan. Going beyond primal treewidth for (M)ILP. In Proc. AAAI 2017, pages 815-821, 2017. Google Scholar
  16. Michel X. Goemans and Thomas Rothvoß. Polynomiality for bin packing with a constant number of item types. In Proc. SODA 2014, pages 830-839. ACM, New York, 2014. Google Scholar
  17. Jens Gramm, Rolf Niedermeier, and Peter Rossmanith. Fixed-parameter algorithms for closest string and related problems. Algorithmica, 37(1):25-42, 2003. Google Scholar
  18. Raymond Hemmecke, Matthias Köppe, and Robert Weismantel. Graver basis and proximity techniques for block-structured separable convex integer minimization problems. Math. Program., 145(1-2, Ser. A):1-18, 2014. Google Scholar
  19. Raymond Hemmecke, Shmuel Onn, and Lyubov Romanchuk. n-fold integer programming in cubic time. Math. Program., 137(1-2, Ser. A):325-341, 2013. Google Scholar
  20. Raymond Hemmecke, Shmuel Onn, and Robert Weismantel. A polynomial oracle-time algorithm for convex integer minimization. Math. Program., 126(1, Ser. A):97-117, 2011. Google Scholar
  21. Danny Hermelin and Liat Rozenberg. Parameterized complexity analysis for the closest string with wildcards problem. Theoret. Comput. Sci., 600:11-18, 2015. Google Scholar
  22. Bart M. P. Jansen and Stefan Kratsch. A structural approach to kernels for ILPs: Treewidth and total unimodularity. In Proc. ESA 2015, volume 9294 of Lecture Notes Comput. Sci., pages 779-791, 2015. Google Scholar
  23. Ravi Kannan. Minkowski’s convex body theorem and integer programming. Math. Oper. Res., 12(3):415-440, 1987. Google Scholar
  24. Leonid Khachiyan and Lorant Porkolab. Integer optimization on convex semialgebraic sets. Discrete Comput. Geom., 23(2):207-224, 2000. Google Scholar
  25. Dušan Knop and Martin Koutecký. Scheduling meets n-fold integer programming. Journal of Scheduling, page to appear, 2017. Google Scholar
  26. Dušan Knop, Martin Koutecký, and Matthias Mnich. Combinatorial n-fold integer programming and applications. Technical report, 2017. URL: https://arxiv.org/abs/1705.08657.
  27. Dušan Knop, Martin Koutecký, and Matthias Mnich. Voting and bribing in single-exponential time. In Proc. STACS 2017, volume 66 of Leibniz Int. Proc. Informatics, pages 46:1-46:14, 2017. Google Scholar
  28. Stefan Kratsch. On polynomial kernels for sparse integer linear programs. J. Comput. System Sci., 82(5):758-766, 2016. Google Scholar
  29. Michael Lampis. Algorithmic meta-theorems for restrictions of treewidth. Algorithmica, 64(1):19-37, 2012. Google Scholar
  30. Hendrik W. Lenstra, Jr. Integer programming with a fixed number of variables. Mathematics of Operations Research, 8(4):538-548, 1983. Google Scholar
  31. Jesus 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
  32. Daniel Lokshtanov. Parameterized integer quadratic programming: Variables and coefficients. Technical report, 2015. URL: http://arxiv.org/abs/1511.00310.
  33. Matthias Mnich and Andreas Wiese. Scheduling and fixed-parameter tractability. Math. Program., 154(1-2, Ser. B):533-562, 2015. Google Scholar
  34. Rolf Niedermeier. Ubiquitous parameterization - invitation to fixed-parameter algorithms. In Proc. MFCS 2004, volume 3153 of Lecture Notes in Comput. Sci., pages 84-103. Springer, Berlin, 2004. Google Scholar
  35. Shmuel Onn. Nonlinear discrete optimization. Zurich Lectures in Advanced Mathematics, European Mathematical Society, 2010. Google Scholar
  36. Shmuel Onn. Huge multiway table problems. Discrete Optim., 14:72-77, 2014. 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