Journal of the ACM Bibliography
Sartaj Sahni. Approximate
algorithms for the 0/1 knapsack problem. Journal of the
ACM, 22(1):115-124, January 1975.
[BibTeX entry]
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.
Shortcuts: