×

Faster FPTASes for counting and random generation of knapsack solutions. (English) Zbl 1423.68600

Summary: In the #P-complete problem of counting 0/1 Knapsack solutions, the input consists of a sequence of \(n\) nonnegative integer weights \(w_1,\dots,w_n\) and an integer \(C\), and we have to find the number of subsequences (subsets of indices) with total weight at most \(C\). We give faster and simpler fully polynomial-time approximation schemes (FPTASes) for this problem, and for its random generation counterpart. Our method is based on dynamic programming and discretization of large numbers through floating-point arithmetic. We improve both deterministic counting FPTASes from [P. Gopalan et al., in: Proceedings of the 52nd annual IEEE symposium on foundations of computer science, FOCS’11. Los Alamitos, CA: IEEE Computer Society. 817–826 (2011; Zbl 1292.68167); D. Štefankovič et al., SIAM J. Comput. 41, No. 2, 356–366 (2012; Zbl 1253.68182)] and the randomized counting and random generation algorithms in [M. Dyer, in: Proceedings of the 35th annual ACM symposium on theory of computing, STOC’03. New York, NY: ACM Press. 693–699 (2003; Zbl 1192.90242)].
Our method is general, and it can be directly applied on top of combinatorial decompositions (such as dynamic programming solutions) of various problems. For example, we also improve the complexity of the problem of counting 0/1 Knapsack solutions in an arc-weighted DAG.

MSC:

68W25 Approximation algorithms
68W40 Analysis of algorithms
90C27 Combinatorial optimization
90C39 Dynamic programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Rizzi, R.; Tomescu, A. I., Faster FPTASes for counting and random generation of Knapsack solutions, (Schulz, A.; Wagner, D., ESA 2014 - 22nd European Symposium on Algorithms. ESA 2014 - 22nd European Symposium on Algorithms, Lecture Notes in Computer Science, vol. 8737 (2014), Springer-Verlag), 762-773 · Zbl 1425.68459
[2] Mihalák, M.; Šrámek, R.; Widmayer, P., Counting approximately-shortest paths in directed acyclic graphs, Theory Comput. Syst., 58, 1, 45-59 (2016), A preliminary version appeared at WAOA 2013 · Zbl 1332.05073
[3] Jerrum, M.; Valiant, L. G.; Vazirani, V. V., Random generation of combinatorial structures from a uniform distribution, Theor. Comput. Sci., 43, 169-188 (1986) · Zbl 0597.68056
[4] Gopalan, P.; Klivans, A. R.; Meka, R., Polynomial-time approximation schemes for Knapsack and related counting problems using branching programs, CoRR
[5] Dyer, M. E., Approximate counting by dynamic programming, (Larmore, L. L.; Goemans, M. X., STOC (2003), ACM), 693-699 · Zbl 1192.90242
[6] Štefankovič, D.; Vempala, S.; Vigoda, E., A deterministic polynomial-time approximation scheme for counting Knapsack solutions, SIAM J. Comput., 41, 2, 356-366 (2012) · Zbl 1253.68182
[7] Dyer, M. E.; Frieze, A. M.; Kannan, R.; Kapoor, A.; Perkovic, L.; Vazirani, U. V., A mildly exponential time algorithm for approximating the number of solutions to a multidimensional Knapsack problem, Comb. Probab. Comput., 2, 271-284 (1993) · Zbl 0819.90094
[8] Morris, B.; Sinclair, A., Random walks on truncated cubes and sampling 0-1 Knapsack solutions, SIAM J. Comput., 34, 1, 195-226 (2004) · Zbl 1101.68044
[9] Gopalan, P.; Klivans, A.; Meka, R.; Stefankovic, D.; Vempala, S.; Vigoda, E., An FPTAS for #Knapsack and related counting problems, (Ostrovsky, R., FOCS (2011), IEEE), 817-826 · Zbl 1292.68167
[10] Schönhage, A.; Strassen, V., Schnelle multiplikation großer zahlen, Computing, 7, 3-4, 281-292 (1971) · Zbl 0223.68007
[11] Denise, A.; Zimmermann, P., Uniform random generation of decomposable structures using floating-point arithmetic, Theor. Comput. Sci., 218, 2, 233-248 (1999) · Zbl 0933.68154
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.