The efficiency of an algorithm of integer programming: a probabilistic analysis
HTML articles powered by AMS MathViewer
- by Vladimir Lifschitz PDF
- Proc. Amer. Math. Soc. 79 (1980), 72-76 Request permission
Abstract:
A simple algorithm for solving the knapsack problem is shown to lead to examining, on the average, around ${e^{2\sqrt n }}$ vectors out of ${2^n}$.References
- Victor Klee and George J. Minty, How good is the simplex algorithm?, Inequalities, III (Proc. Third Sympos., Univ. California, Los Angeles, Calif., 1969; dedicated to the memory of Theodore S. Motzkin), Academic Press, New York, 1972, pp. 159–175. MR 0332165
- Richard M. Karp, Reducibility among combinatorial problems, Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972) Plenum, New York, 1972, pp. 85–103. MR 0378476
- Ellis Horowitz and Sartaj Sahni, Computing partitions with applications to the knapsack problem, J. Assoc. Comput. Mach. 21 (1974), 277–292. MR 354006, DOI 10.1145/321812.321823
- Donald E. Knuth, Estimating the efficiency of backtrack programs, Math. Comp. 29 (1975), 122–136. MR 373371, DOI 10.1090/S0025-5718-1975-0373371-6
Additional Information
- © Copyright 1980 American Mathematical Society
- Journal: Proc. Amer. Math. Soc. 79 (1980), 72-76
- MSC: Primary 90C10; Secondary 68C25
- DOI: https://doi.org/10.1090/S0002-9939-1980-0560587-2
- MathSciNet review: 560587