Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-23T13:38:51.917Z Has data issue: false hasContentIssue false
  • English
  • Français

A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem

Published online by Cambridge University Press:  12 September 2008

Martin Dyer ,
Alan Frieze ,
Ravi Kannan ,
Ajai Kapoor ,
Ljubomir Perkovic  and
Umesh Vazirani
Martin Dyer
Affiliation:
University of Leeds, Leeds LS2 9JT, UK
Alan Frieze
Affiliation:
Carnegie Mellon University, Pittsburgh PA15213, USA
Ravi Kannan
Affiliation:
Carnegie Mellon University, Pittsburgh PA15213, USA
Ajai Kapoor
Affiliation:
Carnegie Mellon University, Pittsburgh PA15213, USA
Ljubomir Perkovic
Affiliation:
Carnegie Mellon University, Pittsburgh PA15213, USA
Umesh Vazirani
Affiliation:
University of California, Berkeley CA94320, USA
Get access Rights & Permissions [Opens in a new window]

Abstract

We describe a time randomized algorithm that estimates the number of feasible solutions of a multidimensional knapsack problem within 1 ± ε of the exact number. (Here r is the number of constraints and n is the number of integer variables.) The algorithm uses a Markov chain to generate an almost uniform random solution to the problem.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 2 , Issue 3 , September 1993 , pp. 271 - 284
Copyright
Copyright © Cambridge University Press 1993

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1]Applegate, D. and Kannan, R. (1991) Sampling and integration of near log-concave functions. Proc. 23rd ACM Symposium on Theory of Computing 156–163.Google Scholar
[2]Broder, A. Z. (1986) How hard is it to marry at random? (On the approximation of the permanent.) Proceedings of the 18th Annual ACM Symposium on Theory of Computing 50–58. (Erratum in Proceedings of the 20th Annual ACM Symposium on Theory of Computing (1988) 551.)Google Scholar
[3]Dyer, M. E. and Frieze, A. M. (1991) Computing the volume of convex bodies: a case where randomness provably helps. In: Bollobás, B. (ed.) Probabilistic Combinatorics and its Applications. AMS Proceedings of Symposia in Applied Mathematics 44 123–169.CrossRefGoogle Scholar
[4]Dyer, M. E., Frieze, A. M. and Kannan, R. (1991) A random polynomial time algorithm for approximating the volume of convex bodies. Journal of the Association for Computing Machinery 38 1–17.CrossRefGoogle Scholar
[5]Hoeffding, W. (1963) Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association 58 13–30.CrossRefGoogle Scholar
[6]Jerrum, M. R. and Sinclair, A. J. (1989) Approximating the permanent. SIAM Journal on Computing 18 1149–1178.CrossRefGoogle Scholar
[7]Jerrum, M. R. and Sinclair, A. J. (1989) Polynomial-time approximation algorithms for the Ising model, Department of Computer Science, Edinburgh University. (To appear in SIAM Journal on Computing.)Google Scholar
[8]Jerrum, M. R., Valiant, L. G. and Vazirani, V. V. (1986) Random generation of combinatorial structures from a uniform distribution. Theoretical Computer Science 43 169–188.CrossRefGoogle Scholar
[9]Jerrum, M. R. and Vazirani, U. (1992) A mildly exponential approximation algorithm for the permanent. Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computing 320–326.Google Scholar
[10]Karzanov, A. and Khachiyan, L. (1990) On the conductance of order Markov chains. Technical Report DCS TR 268, Rutgers University.Google Scholar
[11]Lovász, L. (1979) Combinatorial problems and exercises, North-Holland, Amsterdam.Google Scholar
[12]Lovász, L. and Simonovits, M. (1990) The mixing rate of Markov chains, an isoperimetric inequality and computing the volume. Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science 346–354.CrossRefGoogle Scholar
[13]Lovász, L. and Simonovits, M. (1992) Random walks in a convex body and an improved volume algorithm. Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science.Google Scholar
[14]Mihail, M. and Winkler, P. (1992) On the number of Euler orientations of a graph. Proceedings of the 3rd Annual ACM-SIAM Symposium on Discrete Algorithms 138–145.Google Scholar
[15]Sinclair, A. J. and Jerrum, M. R. (1989) Approximate counting, uniform generation and rapidly mixing Markov chains. Information and Computation 82 93–133.CrossRefGoogle Scholar