Document Open Access Logo

Integer Programming in Parameterized Complexity: Three Miniatures

Authors Tomás Gavenciak, Dusan Knop, Martin Koutecký

PDF
Thumbnail PDF

File

LIPIcs.IPEC.2018.21.pdf
  • Filesize: 0.58 MB
  • 16 pages

Document Identifiers

Author Details

Tomás Gavenciak
  • Department of Applied Mathematics, Charles University, Prague, Czech Republic
Dusan Knop
  • Department of Informatics, University of Bergen, Bergen, Norway and Department of Theoretical Computer Science, Faculty of Information Technology, Czech Technical University in Prague, Prague, Czech Republic
Martin Koutecký
  • Technion - Israel Institute of Technology, Haifa, Israel and Computer Science Institute, Charles University, Prague, Czech Republic

Funding

  • Knop, Dusan: Author supported by the project NFR MULTIVAL.
  • Koutecký, Martin: Author supported by Technion postdoctoral fellowship.

Cite As Get BibTex

Tomás Gavenciak, Dusan Knop, and Martin Koutecký. Integer Programming in Parameterized Complexity: Three Miniatures. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 21:1-21:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/LIPIcs.IPEC.2018.21

Abstract

Powerful results from the theory of integer programming have recently led to substantial advances in parameterized complexity. However, our perception is that, except for Lenstra's algorithm for solving integer linear programming in fixed dimension, there is still little understanding in the parameterized complexity community of the strengths and limitations of the available tools. This is understandable: it is often difficult to infer exact runtimes or even the distinction between FPT and XP algorithms, and some knowledge is simply unwritten folklore in a different community. We wish to make a step in remedying this situation.
To that end, we first provide an easy to navigate quick reference guide of integer programming algorithms from the perspective of parameterized complexity. Then, we show their applications in three case studies, obtaining FPT algorithms with runtime f(k) poly(n). We focus on: 
- Modeling: since the algorithmic results follow by applying existing algorithms to new models, we shift the focus from the complexity result to the modeling result, highlighting common patterns and tricks which are used. 
- Optimality program: after giving an FPT algorithm, we are interested in reducing the dependence on the parameter; we show which algorithms and tricks are often useful for speed-ups. 
- Minding the poly(n): reducing f(k) often has the unintended consequence of increasing poly(n); so we highlight the common trade-offs and show how to get the best of both worlds. 
Specifically, we consider graphs of bounded neighborhood diversity which are in a sense the simplest of dense graphs, and we show several FPT algorithms for Capacitated Dominating Set, Sum Coloring, and Max-q-Cut by modeling them as convex programs in fixed dimension, n-fold integer programs, bounded dual treewidth programs, and indefinite quadratic programs in fixed dimension.

Subject Classification

ACM Subject Classification
  • Theory of computation → Parameterized complexity and exact algorithms
  • Theory of computation → Graph algorithms analysis
Keywords
  • graph coloring
  • parameterized complexity
  • integer linear programming
  • integer convex programming

Metrics

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

Related Versions

References

  1. Kateřina Altmanová, Dušan Knop, and Martin Kouteckỳ. Evaluating and Tuning n-fold Integer Programming. In Gianlorenzo D'Angelo, editor, 17th International Symposium on Experimental Algorithms, SEA 2018, June 27-29, 2018, L'Aquila, Italy, volume 103 of LIPIcs, pages 10:1-10:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.SEA.2018.10.
  2. Sancrey Rodrigues Alves, Konrad Kazimierz Dabrowski, Luérbio Faria, Sulamita Klein, Ignasi Sau, and Uéverton dos Santos Souza. On the (Parameterized) Complexity of Recognizing Well-Covered (r, l)-graphs. In 10th International Conference on Combinatorial Optimization and Applications (COCOA'16), volume 10043 of Lecture Notes in Computer Science, pages 423-437, 2016. URL: http://dx.doi.org/10.1007/978-3-319-48749-6.
  3. NR Aravind, Subrahmanyam Kalyanasundaram, Anjeneya Swami Kare, and Juho Lauri. Algorithms and hardness results for happy coloring problems. arXiv preprint arXiv:1705.08282, 2017. Google Scholar
  4. Matthias Aschenbrenner and Raymond Hemmecke. Finiteness theorems in stochastic integer programming. Foundations of Computational Mathematics, 7(2):183-227, 2007. Google Scholar
  5. Johannes Bisschop. AIMMS Optimization Modeling. Paragon Decision Technology BV, 2006. Google Scholar
  6. Édouard Bonnet and Florian Sikora. The Graph Motif problem parameterized by the structure of the input graph. Discrete Applied Mathematics, 2016. Google Scholar
  7. Robert Bredereck, Jiehua Chen, Piotr Faliszewski, Jiong Guo, Rolf Niedermeier, and Gerhard J Woeginger. Parameterized algorithmics for computational social choice: Nine research challenges. Tsinghua Science and Technology, 19(4):358-373, 2014. Google Scholar
  8. 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
  9. Lin Chen and Daniel 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
  10. Jason Crampton, Gregory Gutin, Martin Koutecký, and Rémi Watrigant. Parameterized resiliency problems via integer linear programming. In Proc. CIAC 2017, volume 10236 of Lecture Notes Comput. Sci., pages 164-176, 2017. Google Scholar
  11. Daniel Dadush, Chris Peikert, and Santosh Vempala. Enumerative Lattice Algorithms in any Norm Via M-ellipsoid Coverings. In Rafail Ostrovsky, editor, FOCS, page 580–589. IEEE, 2011. URL: http://dx.doi.org/10.1109/FOCS.2011.31.
  12. Daniel Dadush and Santosh S Vempala. Near-optimal deterministic algorithms for volume computation via M-ellipsoids. Proceedings of the National Academy of Sciences, 110(48):19237-19245, 2013. Google Scholar
  13. Michael Dom, Daniel Lokshtanov, Saket Saurabh, and Yngve Villanger. Capacitated domination and covering: A parameterized perspective. In International Workshop on Parameterized and Exact Computation, pages 78-90. Springer, 2008. Google Scholar
  14. Rodney G. Downey and Michael R. Fellows. Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, 2013. URL: http://dx.doi.org/10.1007/978-1-4471-5559-1.
  15. Friedrich Eisenbrand, Christoph Hunkenschröder, and Kim-Manuel Klein. Faster Algorithms for Integer Programs with Block Structure. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 49:1-49:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2018.49.
  16. Friedrich Eisenbrand and Gennady Shmonin. Parametric integer programming in fixed dimension. Math. Oper. Res., 33(4), 2008. Google Scholar
  17. Friedrich Eisenbrand and Robert Weismantel. Proximity results and faster algorithms for Integer Programming using the Steinitz Lemma. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 808-816. SIAM, 2018. Google Scholar
  18. Piotr Faliszewski, Rica Gonen, Martin Koutecký, and Nimrod Talmon. Opinion diffusion and campaigning on society graphs. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18, pages 219-225. International Joint Conferences on Artificial Intelligence Organization, 7 2018. URL: http://dx.doi.org/10.24963/ijcai.2018/30.
  19. Michael R. Fellows, Daniel Lokshtanov, Neeldhara Misra, Frances A. Rosamond, and Saket Saurabh. Graph Layout Problems Parameterized by Vertex Cover. In Seok-Hee Hong, Hiroshi Nagamochi, and Takuro Fukunaga, editors, ISAAC, volume 5369 of Lecture Notes in Computer Science, page 294–305. Springer, 2008. URL: http://dx.doi.org/10.1007/978-3-540-92182-0.
  20. 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 Applied Mathematics, 2017. Google Scholar
  21. Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, and Saket Saurabh. Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width. SIAM J. Comput., 43(5):1541-1563, 2014. URL: http://dx.doi.org/10.1137/130910932.
  22. András Frank and Eva Tardos. An application of simultaneous diophantine approximation in combinatorial optimization. Combinatorica, 7(1):49-65, 1987. URL: http://dx.doi.org/10.1007/BF02579200.
  23. Jakub Gajarský, Petr Hliněný, Martin Koutecký, and Shmuel Onn. Parameterized shifted combinatorial optimization. In International Computing and Combinatorics Conference, pages 224-236. Springer, 2017. Google Scholar
  24. Robert Ganian. Using neighborhood diversity to solve hard problems. arXiv preprint arXiv:1201.3091, 2012. Google Scholar
  25. Luisa Gargano and Adele A. Rescigno. Complexity of conflict-free colorings of graphs. Theoretical Computer Science, 566(??):39-49, February 2015. URL: http://www.sciencedirect.com/science/article/pii/S0304397514009463.
  26. Martin Grötschel, László Lovász, and Alexander Schrijver. Geometric algorithms and combinatorial optimization, volume 2. Springer Science &Business Media, 2012. Google Scholar
  27. Sebastian Heinz. Complexity of integer quasiconvex polynomial optimization. J. Complexity, 21(4):543–556, 2005. URL: http://dx.doi.org/10.1016/j.jco.2005.04.004.
  28. Raymond Hemmecke, Shmuel Onn, and Lyubov Romanchuk. n-Fold integer programming in cubic time. Math. Program, 137(1-2):325-341, 2013. URL: http://dx.doi.org/10.1007/s10107-011-0490-y.
  29. Raymond Hemmecke and Rüdiger Schultz. Decomposition methods for two-stage stochastic integer programs. In Online optimization of large scale systems, pages 601-622. Springer, 2001. Google Scholar
  30. Danny Hermelin, Judith-Madeleine Kubitza, Dvir Shabtay, Nimrod Talmon, and Gerhard Woeginger. Scheduling two competing agents when one agent has significantly fewer jobs. In LIPIcs-Leibniz International Proceedings in Informatics, volume 43. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015. Google Scholar
  31. Robert Hildebrand and Matthias Köppe. A new Lenstra-type algorithm for quasiconvex polynomial integer minimization with complexity 2^O(nlogn). Discrete Optimization, 10(1):69–84, 2013. URL: http://dx.doi.org/10.1016/j.disopt.2012.11.003.
  32. Klaus Jansen. Complexity results for the optimum cost chromatic partition problem. Manuscript, 1997. Google Scholar
  33. 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
  34. Klaus Jansen and Lars Rohwedder. On Integer Programming and Convolution. arXiv preprint arXiv:1803.04744, 2018. Google Scholar
  35. Klaus Jansen and Roberto Solis-Oba. An OPT+ 1 Algorithm for the Cutting Stock Problem with Constant Number of Object Lengths. In IPCO, pages 438-449. Springer, 2010. Google Scholar
  36. Ravi Kannan. Minkowski’s convex body theorem and integer programming. Math. Oper. Res., 12(3):415–440, August 1987. Google Scholar
  37. Leonid Khachiyan and Lorant Porkolab. Integer Optimization on Convex Semialgebraic Sets. Discrete &Computational Geometry, 23(2):207–224, 2000. URL: http://dx.doi.org/10.1007/PL00009496.
  38. Dušan Knop and Martin Koutecký. Scheduling meets n-fold Integer Programming. Journal of Scheduling, November 2017. URL: http://dx.doi.org/10.1007/s10951-017-0550-0.
  39. Dušan Knop, Martin Koutecký, and Matthias Mnich. Combinatorial n-fold Integer Programming and Applications. In Kirk Pruhs and Christian Sohler, editors, 25th Annual European Symposium on Algorithms (ESA 2017), volume 87 of Leibniz International Proceedings in Informatics (LIPIcs), pages 54:1-54:14, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2017.54.
  40. Dušan Knop, Martin Koutecký, and Matthias Mnich. Voting and Bribing in Single-Exponential Time. In Heribert Vollmer and Brigitte Vallée, editors, 34th Symposium on Theoretical Aspects of Computer Science, STACS 2017, March 8-11, 2017, Hannover, Germany, volume 66 of LIPIcs, pages 46:1-46:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  41. Dušan Knop, Tomáš Masařík, and Tomáš Toufar. Parameterized Complexity of Fair Vertex Evaluation Problems. CoRR, abs/1803.06878, 2018. URL: http://arxiv.org/abs/1803.06878.
  42. Dušan Knop, Martin Koutecký, and Matthias Mnich. A Unifying Framework for Manipulation Problems. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS 2018, Stockholm, Sweden, July 10-15, 2018, pages 256-264, 2018. URL: http://dl.acm.org/citation.cfm?id=3237427.
  43. Martin Koutecký, Asaf Levin, and Shmuel Onn. A Parameterized Strongly Polynomial Algorithm for Block Structured Integer Programs. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 85:1-85:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2018.85.
  44. Michael Lampis. Algorithmic Meta-theorems for Restrictions of Treewidth. Algorithmica, 64(1):19-37, 2012. Google Scholar
  45. Hendrik W. Lenstra, Jr. Integer programming with a fixed number of variables. Mathematics of Operations Research, 8(4):538-548, 1983. Google Scholar
  46. Daniel Lokshtanov. New Methods in Parameterized Algorithms and Complexity. PhD thesis, University of Bergen, 2009. Google Scholar
  47. Daniel Lokshtanov. Parameterized integer quadratic programming: Variables and coefficients. arXiv preprint arXiv:1511.00310, 2015. Google Scholar
  48. Daniel Lokshtanov, MS Ramanujan, and Saket Saurabh. A linear time parameterized algorithm for directed feedback vertex set. arXiv preprint arXiv:1609.04347, 2016. Google Scholar
  49. Dániel Marx. What’s next? Future directions in parameterized complexity. In The Multivariate Algorithmic Revolution and Beyond, pages 469-496. Springer, 2012. Google Scholar
  50. Tomáš Masařík and Tomáš Toufar. Parameterized Complexity of Fair Deletion Problems. In International Conference on Theory and Applications of Models of Computation (TAMC'16), pages 628-642, 2017. Google Scholar
  51. Matthias Mnich and Andreas Wiese. Scheduling and fixed-parameter tractability. Math. Program., 154(1-2, Ser. B):533-562, 2015. Google Scholar
  52. Rolf Niedermeier. Ubiquitous Parameterization - Invitation to Fixed-Parameter Algorithms. In Jirí Fiala, Václav Koubek, and Jan Kratochvíl, editors, MFCS, volume 3153 of Lecture Notes in Computer Science, page 84–103. Springer, 2004. URL: http://dx.doi.org/10.1007/978-3-540-28629-5_4.
  53. Timm Oertel, Christian Wagner, and Robert Weismantel. Integer convex minimization by mixed integer linear optimization. Oper. Res. Lett, 42(6-7):424-428, 2014. URL: http://dx.doi.org/10.1016/j.orl.2014.07.005.
  54. Christos H Papadimitriou. On the complexity of integer programming. Journal of the ACM (JACM), 28(4):765-768, 1981. Google Scholar
  55. Kevin Zemmer. Integer Polynomial Optimization in Fixed Dimension. PhD thesis, ETH Zurich, 2017. 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