Approximate counting by dynamic programming

ABSTRACT

We give efficient algorithms to sample uniformly, and count approximately, the solutions to a zero-one knapsack problem. The algorithm is based on using dynamic programming to provide a deterministic relative approximation. Then "dart throwing" techniques are used to give arbitrary approximation ratios. We also indicate how further improvements can be obtained using randomized rounding. We extend the approach to several related problems: the m-constraint zero-one knapsack, the general integer knapsack (including its m-constraint version) and contingency tables with constantly many rows.

REFERENCES

• 1: F. R. K. Chung , R. L. Graham , S.-T. Yau, On sampling with Markov chains, Random Structures & Algorithms, v.9 n.1-2, p.55-77, Aug./Sept. 1996
• 2: Mary Cryan , Martin Dyer, A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509946]
• 3: Mary Cryan , Martin E. Dyer , Leslie Ann Goldberg , Mark Jerrum , Russell A. Martin, Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.711-720, November 16-19, 2002
• 4: J. De Loera and B. Sturmfels. Algebraic unimodular counting. Preprint, University of California at Davis, 2001.
• 5: P. Diaconis and B. Efron. Testing for independence in a two-way table: new interpretations of the chi-square statistic (with discussion). Annals of Statistics, 13, 1995,pp. 845--913.
• 6: P. Diaconis and A. Gangolli, Rectangular arrays with fixed margins. In Discrete Probability and Algorithms (D. Aldous, P. Varaiya, J. Spencer and J. Steele, Eds.), IMA Volumes on Mathematics and its Applications, 72, Springer, New York, 1995, pp. 15--41.
• 7: P. Diaconis and L. Saloff-Coste. Random walk on contingency tables with fixed row and column sums. Technical Report, Department of Mathematics, Harvard University, 1995.
• 8: M. Dyer, A. Frieze, R. Kannan, A. Kapoor, L. Perkovic and U. Vazirani. A mildly exponential algorithm for estimating the number of knapsack solutions. Combinatorics, Probability and Computing, 2, 1993, pp. 271--284.
• 9: Martin Dyer , Catherine Greenhill, Polynomial-time counting and sampling of two-rowed contingency tables, Theoretical Computer Science, v.246 n.1-2, p.265-278, Sept 2000 [doi>10.1016/S0304-3975(99)00136-X]
• 10: Martin Dyer , Ravi Kannan , John Mount, Sampling contingency tables, Random Structures & Algorithms, v.10 n.4, p.487-506, July 1997 [doi>10.1002/(SICI)1098-2418(199707)10:4<487::AID-RSA4>3.0.CO;2-Q]
• 11: Diane Hernek, Random generation of 2 × n contingency tables, Random Structures & Algorithms, v.13 n.1, p.71-79, Aug. 1998 [doi>10.1002/(SICI)1098-2418(199808)13:1<71::AID-RSA4>3.0.CO;2-P]
• 12: W. Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58, 1963, pp .13--30.
• 13: M. Jerrum, Counting, sampling and integrating: algorithms and complexity, Birkhauser, Basel, 2003.
• 14: Ben Morris, Improved Bounds for Sampling Contingency Tables, Proceedings of the Third International Workshop on Approximation Algorithms for Combinatorial Optimization Problems: Randomization, Approximation, and Combinatorial Algorithms and Techniques, p.121-129, August 08-11, 1999
• 15: Benjamin James Morris , Alistair Sinclair, Random walks in convex sets, 2000
• 16: Ben Morris , Alistair Sinclair, Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions, Proceedings of the 40th Annual Symposium on Foundations of Computer Science, p.230, October 17-18, 1999
• 17: B. Morris and A. Sinclair, Random walks on truncated cubes and sampling 0-1 knapsack solutions, July 2002, submitted. (An extended and improved version of{16}.)
• 18: J. Mount, Application of convex sampling to optimization and contingency table generation. PhD thesis, Technical report CMU-CS-95-152, Computer Science Department, Carnegie Mellon University, 1995.
• 19: Alistair Sinclair , Mark Jerrum, Approximate counting, uniform generation and rapidly mixing Markov chains, Information and Computation, v.82 n.1, p.93-133, July 1989 [doi>10.1016/0890-5401(89)90067-9]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS

General Terms:
Algorithms, Theory