LIPIcs.ITCS.2019.43.pdf
- Filesize: 472 kB
- 17 pages
Document
On Integer Programming and Convolution
Authors
-
Part of:
Volume:
10th Innovations in Theoretical Computer Science Conference (ITCS 2019)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Innovations in Theoretical Computer Science Conference (ITCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2019-01-08
Cite As Get BibTex
Klaus Jansen and Lars Rohwedder. On Integer Programming and Convolution. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 124, pp. 43:1-43:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
https://doi.org/10.4230/LIPIcs.ITCS.2019.43
Abstract
Integer programs with a constant number of constraints are solvable in pseudo-polynomial time. We give a new algorithm with a better pseudo-polynomial running time than previous results. Moreover, we establish a strong connection to the problem (min, +)-convolution. (min, +)-convolution has a trivial quadratic time algorithm and it has been conjectured that this cannot be improved significantly. We show that further improvements to our pseudo-polynomial algorithm for any fixed number of constraints are equivalent to improvements for (min, +)-convolution. This is a strong evidence that our algorithm's running time is the best possible. We also present a faster specialized algorithm for testing feasibility of an integer program with few constraints and for this we also give a tight lower bound, which is based on the SETH.
Subject Classification
ACM Subject Classification
- Theory of computation → Integer programming
- Theory of computation → Dynamic programming
Keywords
- Integer programming
- convolution
- dynamic programming
- SETH
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Amir Abboud, Karl Bringmann, Danny Hermelin, and Dvir Shabtay. SETH-Based Lower Bounds for Subset Sum and Bicriteria Path. CoRR, abs/1704.04546, 2017. URL: http://arxiv.org/abs/1704.04546.
- Kyriakos Axiotis and Christos Tzamos. Capacitated Dynamic Programming: Faster Knapsack and Graph Algorithms. CoRR, abs/1802.06440, 2018. URL: http://arxiv.org/abs/1802.06440.
- Arturs Backurs, Piotr Indyk, and Ludwig Schmidt. Better Approximations for Tree Sparsity in Nearly-Linear Time. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 2215-2229, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.145.
- David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, Mihai Patrascu, and Perouz Taslakian. Necklaces, Convolutions, and X+Y. Algorithmica, 69(2):294-314, 2014. URL: http://dx.doi.org/10.1007/s00453-012-9734-3.
- Karl Bringmann. A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19, pages 1073-1084, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.69.
- Timothy M. Chan and Moshe Lewenstein. Clustered Integer 3SUM via Additive Combinatorics. In Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015, pages 31-40, 2015. URL: http://dx.doi.org/10.1145/2746539.2746568.
- Marek Cygan, Marcin Mucha, Karol Wegrzycki, and Michal Wlodarczyk. On Problems Equivalent to (min, +)-Convolution. In 44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, July 10-14, 2017, Warsaw, Poland, pages 22:1-22:15, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2017.22.
- 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, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 808-816, 2018. URL: http://dx.doi.org/10.1137/1.9781611975031.52.
- Fedor V. Fomin, Fahad Panolan, M. S. Ramanujan, and Saket Saurabh. On the Optimality of Pseudo-polynomial Algorithms for Integer Programming. In 26th Annual European Symposium on Algorithms, ESA 2018, August 20-22, 2018, Helsinki, Finland, pages 31:1-31:13, 2018. URL: http://dx.doi.org/10.4230/LIPIcs.ESA.2018.31.
- Klaus Jansen, Kim-Manuel Klein, and José Verschae. Closing the Gap for Makespan Scheduling via Sparsification Techniques. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy, pages 72:1-72:13, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.ICALP.2016.72.
- Hendrik W. Lenstra Jr. Integer Programming with a Fixed Number of Variables. Math. Oper. Res., 8(4):538-548, 1983. URL: http://dx.doi.org/10.1287/moor.8.4.538.
- Ravi Kannan. Minkowski’s Convex Body Theorem and Integer Programming. Math. Oper. Res., 12(3):415-440, 1987. URL: http://dx.doi.org/10.1287/moor.12.3.415.
-
Hans Kellerer, Ulrich Pferschy, and David Pisinger. Knapsack problems. Springer, 2004.
- Eduardo Sany Laber, Wilfredo Bardales Roncalla, and Ferdinando Cicalese. On lower bounds for the Maximum Consecutive Subsums Problem and the (min, +)-convolution. In 2014 IEEE International Symposium on Information Theory, Honolulu, HI, USA, June 29 - July 4, 2014, pages 1807-1811, 2014. URL: http://dx.doi.org/10.1109/ISIT.2014.6875145.
- Christos H. Papadimitriou. On the complexity of integer programming. J. ACM, 28(4):765-768, 1981. URL: http://dx.doi.org/10.1145/322276.322287.
-
Sergey Vasil'evich Sevast'janov. Approximate solution of some problems in scheduling theory. Metody Diskret. Analiz, 32:66-75, 1978. in Russian.
-
Ernst Steinitz. Bedingt konvergente Reihen und konvexe Systeme. Journal für die reine und angewandte Mathematik, 143:128-176, 1913.