On finding the exact solution of a zero-one knapsack problem

ABSTRACT

Given a 0-1 knapsack problem with input drawn from a certain probability distribution, we show that for every &egr; > 0, there is a self-checking polynomial-time algorithm that finds an optimal solution with probability at least 1 -&egr;. We also prove some upper and lower bounds on random variables related to the problem.

REFERENCES

• 1: E. Balas and E. Zemel, "An Algorithm for Large Zero-One Knapsack Problems", Operations Research, Vol. 28, No.5, 1130-1154 (1980).
• 2: V. Chvatal, "Hard Knapsack Problems", Operations Research, Vol. 28, No.6, (1980).
• 3: W. Feller, "An Introduction to Probability Theory and Its Applications", Wiley & Sons (1971), Vol. 1, 153-154.
• 4: W. Feller, "An Introduction to Probability Theory and Its Applications", Wiley & Sons (1971) Vol. 2, 535.
• 5: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 6: J .C. Lagarias and A. M. Odlyzko, "Solving Low-Density Subset Sum Problems", Proc. 24th IEEE Symposium on Foundations of Computer Science (1983), 1-10.
• 7: G. S. Lueker, "On the Average Difference Between the Solutions to Linear and Integer Knapsack Problems", Applied Probability - Computer Science, the Interface, Vol. 1, Birkhauser (1982).
• 8: A. Renyi, "Probability Theory", North Holland Publishing Company, Amsterdam (1970) 387.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sequencing and scheduling

General Terms:
Algorithms, Theory