Document Open Access Logo

A Deterministic Fully Polynomial Time Approximation Scheme For Counting Integer Knapsack Solutions Made Easy

Author Nir Halman

PDF

File

Thumbnail PDF
PDF
LIPIcs.APPROX-RANDOM.2016.9.pdf
  • Filesize: 0.51 MB
  • 11 pages

Document Identifiers

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)
    0
    PDF Downloads
    0
    Metadata Views

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.

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

Author Details

Nir Halman

References

  1. 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. Google Scholar
  2. 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. Google Scholar
  3. 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. Google Scholar
  4. 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. Google Scholar
  5. 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. Google Scholar
  6. 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. Google Scholar
  7. N. Megiddo. On the complexity of linear programming. In Advances in economic theory, pages 225-268, Cambridge, UK, 1989. Econom. Soc. Monogr. 12. Google Scholar
  8. 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. Google Scholar
  9. 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. Google Scholar
  10. 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. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact