The efficiency of an algorithm of integer programming: a probabilistic analysis

Author:
Vladimir Lifschitz

Journal:
Proc. Amer. Math. Soc. **79** (1980), 72-76

MSC:
Primary 90C10; Secondary 68C25

MathSciNet review:
560587

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A simple algorithm for solving the knapsack problem is shown to lead to examining, on the average, around vectors out of .

**[1]**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****[2]**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****[3]**Ellis Horowitz and Sartaj Sahni,*Computing partitions with applications to the knapsack problem*, J. Assoc. Comput. Mach.**21**(1974), 277–292. MR**0354006****[4]**Donald E. Knuth,*Estimating the efficiency of backtrack programs*, Math. Comp.**29**(1975), 122–136. Collection of articles dedicated to Derrick Henry Lehmer on the occasion of his seventieth birthday. MR**0373371**, 10.1090/S0025-5718-1975-0373371-6

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC:
90C10,
68C25

Retrieve articles in all journals with MSC: 90C10, 68C25

Additional Information

DOI:
http://dx.doi.org/10.1090/S0002-9939-1980-0560587-2

Keywords:
Knapsack problem,
algorithm analysis,
average computing time

Article copyright:
© Copyright 1980
American Mathematical Society