Additional Key Words and Phrases: knapsack problem, approximation, algorithm, efficiency
Selected papers that cite this one
- Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3):501-555, May 1998.
- O. Etzioni, S. Hanks, T. Jiang, R. M. Karp, O. Madani, and O. Waarts. Efficient information gathering on the Internet (extended abstract). In 37th Annual Symposium on Foundations of Computer Science, pages 234-243, Burlington, Vermont, 14-16 October 1996. IEEE.
- Sanjeev Khanna and Rajeev Motwani. Towards a syntactic characterization of PTAS. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 329-337, Philadelphia, Pennsylvania, 22-24 May 1996.
Selected references
- Ellis Horowitz and Sartaj Sahni. Computing partitions with applications to the knapsack problem. Journal of the ACM, 21(2):277-292, April 1974.
- David S. Johnson. Approximation algorithms for combinatorial problems. In Conference Record of Fifth Annual ACM Symposium on Theory of Computing, pages 38-49, Austin, Texas, 30 April-2 May 1973.
- Sartaj Sahni. Some related problems from network flows, game theory and integer programming. In 13th Annual Symposium on Switching and Automata Theory, pages 130-138, The University of Maryland, 25-27 October 1972. IEEE.