LIPIcs.APPROX-RANDOM.2016.9.pdf
- Filesize: 0.51 MB
- 11 pages
Document
A Deterministic Fully Polynomial Time Approximation Scheme For Counting Integer Knapsack Solutions Made Easy
Author
-
Part of:
Volume:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Randomization and Computation (RANDOM)
Conference: International Conference on Approximation Algorithms for Combinatorial Optimization Problems (APPROX) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-09-06
Cite As Get BibTex
Nir Halman. A Deterministic Fully Polynomial Time Approximation Scheme For Counting Integer Knapsack Solutions Made Easy. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 60, pp. 9:1-9:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.APPROX-RANDOM.2016.9
Abstract
Given n elements with nonnegative integer weights w=(w_1,...,w_n), an integer capacity C and positive integer ranges u=(u_1,...,u_n), we consider the counting version of the classic integer knapsack problem: find the number of distinct multisets whose weights add up to at most C. We give a deterministic algorithm that estimates the number of solutions to within relative error epsilon in time polynomial in n, log U and 1/epsilon, where U=max_i u_i. More precisely, our algorithm runs in O((n^3 log^2 U)/epsilon) log (n log U)/epsilon) time. This is an improvement of n^2 and 1/epsilon (up to log terms) over the best known deterministic algorithm by Gopalan et al. [FOCS, (2011), pp. 817-826]. Our algorithm is relatively simple, and its analysis is rather elementary. Our results are achieved by means of a careful formulation of the problem as a dynamic program, using the notion of binding constraints.
Subject Classification
Keywords
- Approximate counting
- integer knapsack
- dynamic programming
- bounding constraints
- $K$-approximating sets and functions
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
M. E. Dyer. Approximate counting by dynamic programming. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing (STOC), June 9-11, 2003, San Diego, CA, USA, pages 693-699, 2003.
-
P. Gopalan, A. Klivans, and R. Meka. Polynomial-time approximation schemes for Knapsack and related counting problems using branching programs. CoRR, abs/1008.3187, 2010.
-
P. Gopalan, A. Klivans, R. Meka, D. Štefankovič, S. Vempala, and E. Vigoda. An FPTAS for #Knapsack and related counting problems. In IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), pages 817-826, 2011.
-
N. Halman, D. Klabjan, C.-L. Li, J. Orlin, and D. Simchi-Levi. Fully polynomial time approximation schemes for stochastic dynamic programs. SIAM Journal on Discrete Mathematics, 28:1725-1796, 2014.
-
N. Halman, D. Klabjan, M. Mostagir, J. Orlin, and D. Simchi-Levi. A fully polynomial time approximation scheme for single-item stochastic inventory control with discrete demand. Mathematics of Operations Research, 34:674-685, 2009.
-
M. Jerrum and A. Sinclair. The Markov chain Monte Carlo method: An approach to approximate counting and integration. In D.S. Hochbaum, editor, Approximation Algorithms for NP-hard Problems, pages 482-520. PWS Publishing Company, Boston, 1996.
-
N. Megiddo. On the complexity of linear programming. In Advances in economic theory, pages 225-268, Cambridge, UK, 1989. Econom. Soc. Monogr. 12.
-
R. Meka and D. Zuckerman. Pseudorandom generators for polynomial threshold functions. In Proceedings of the 42nd ACM Symposium on Theory of Computing (STOC), pages 427-436, 2010.
-
R. Rizzi and A. Tomescu. Faster FPTASes for counting and random generation of knapsack solutions. In Proceedings of the 22nd Annual European Symposium on Algorithms (ESA), pages 762-773, 2014.
-
D. Štefankovič, S. Vempala, and E. Vigoda. A deterministic polynomial-time approximation scheme for counting knapsack solutions. SIAM Journal on Computing, 41:356-366, 2012.