×

The efficiency of an algorithm of integer programming: A probabilistic analysis. (English) Zbl 0456.90054


MSC:

90C09 Boolean programming
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[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. · Zbl 0297.90047
[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.
[3] Ellis Horowitz and Sartaj Sahni, Computing partitions with applications to the knapsack problem, J. Assoc. Comput. Mach. 21 (1974), 277 – 292. · Zbl 0329.90046 · doi:10.1145/321812.321823
[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. · Zbl 0297.68037
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.