Worst-case analysis of greedy algorithms for the subset-sum problem. (English) Zbl 0527.90072


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


[1] M.L. Fisher, ”Worst-case analysis of heuristic algorithms,”Management Science 26 (1980) 1–17. · Zbl 0448.90041 · doi:10.1287/mnsc.26.1.1
[2] M.R. Garey and D.S. Johnson,Computers and intractability: a guide to the theory of NP-completeness (Freeman, San Francisco, 1979). · Zbl 0411.68039
[3] G.V. Gens and E.V. Levner, ”Fast approximation algorithms for knapsack type problems,” in: K. Iracki, K. Malanowski and S. Walukiewicz, eds.,Optimization techniques, Part 2, Lecture Notes in Control and Information Sciences 23 (Springer, Berlin, 1980) pp. 185–194. · Zbl 0444.90074
[4] O.H. Ibarra and C.E. Kim, ”Fast approximation algorithms for the knapsack and sum of subset problems,”Journal of the ACM 22 (1975) 463–468. · Zbl 0345.90049 · doi:10.1145/321906.321909
[5] D.S. Johnson, ”Approximation algorithms for combinatorial problems,”Journal of Computer and System Sciences 9 (1974) 256–278. · Zbl 0296.65036 · doi:10.1016/S0022-0000(74)80044-9
[6] E. L. Lawler, ”Fast approximation algorithms for knapsack problems,”Mathematics of Operations Research 4 (1979) 339–356. · Zbl 0425.90064 · doi:10.1287/moor.4.4.339
[7] S. Sahni, ”Approximate algorithms for the 0/1 knapsack problem,”Journal of the ACM 22 (1975) 115–124. · Zbl 0362.90066 · doi:10.1145/321864.321873
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.