A Polynomial Linear Search Algorithm for the n-Dimensional Knapsack Problem

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A Polynomial Linear Search Algorithm for the n-Dimensional Knapsack Problem

Full text

Pdf (477 KB)

Source

Journal of the ACM (JACM) archive
Volume 31 , Issue 3 (July 1984) table of contents

Pages: 668 - 676

Year of Publication: 1984

ISSN:0004-5411

Author

Friedhelm Meyer auf der Heide

Fachbereich 20 (Informatik), Johann Wolfgang Goethe Universitat, Mertonstrasse 17-25, 6000 Frankfurt am Main, West Germany

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 6, Downloads (12 Months): 37, Citation Count: 16

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/828.322450 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
	2	JIAWEI, H. On lower bounds of time complexity of some algorithms. Sa. Smlca 23, 8/9 (1976), 890-900.
	3	SIMON, J., AND PAUL, W.J. Decision trees and random access machines. In Monographic 30, L'Enseignement Mathematique, Logic et Algorithmic. Univ. Geneva, Switzerland, 1982, pp.331- 340.
	4	DOBKIN, D., AND LIPTON, R.J. A lower bound of (I/2)n 2 on linear search programs for the knapsack problem. J Comput. Syst Sci 16 (1978), 413-417.
	5	KLEIN, P., AND MEYER AUF DER HEIDE, F. A lower time bound for the knapsack problem on random access machines. Acta Inf. 19 (1983), 385-395.
	6	DOBKIN, D. AND LIPTON, R.J. On some generalizations of binary search. Preprint.
	7	Andrew Chi-Chih Yao, On the parallel computation for the knapsack problem, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.123-127, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802465]
	8	ASPVALL, B., AND STONE, R.E. Khachtyan's linear programming algorithm. J. Alg 1 (1980), 1- 13.
	9	GRUNBAUM, B. Convex Polytopes. Wdey, New York, 1967.
	10	BLASCHKE, W. Uber den groten Kreis in einer konvexen Punktmenge. Jahresbericht DMV 23 (1914), S.369-374.

CITED BY 16

	Ménard Bourgade, Calculs sur les structures de langage dénombrable, Theoretical Computer Science, v.270 n.1-2, p.205-222, January
	Hervé Fournier , Pascal Koiran, Are lower bounds easier over the reals?, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.507-513, May 24-26, 1998, Dallas, Texas, United States
	Anders Björner , László Lovász , Andrew C. C. Yao, Linear decision trees: volume estimates and topological bounds, Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, p.170-177, May 04-06, 1992, Victoria, British Columbia, Canada
	Dima Grigoriev , Marek Karpinski, Randomized Ω(n²) lower bound for knapsack, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.76-85, May 04-06, 1997, El Paso, Texas, United States
	Jeff Erickson, Lower bounds for linear satisfiability problems, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.388-395, January 22-24, 1995, San Francisco, California, United States
	Dima Grigoriev , Marek Karpinski , Friedhelm Meyer auf der Heide , Roman Smolensky, A lower bound for randomized algebraic decision trees, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.612-619, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Friedhelm Meyer auf der Heide, Fast algorithms for N-dimensional restrictions of hard problems, Journal of the ACM (JACM), v.35 n.3, p.740-747, July 1988
	Jun Xu , Richard J. Lipton, On fundamental tradeoffs between delay bounds and computational complexity in packet scheduling algorithms, ACM SIGCOMM Computer Communication Review, v.32 n.4, October 2002
	Friedhelm Meyer auf der Heide, Lower bounds for solving linear diophantine equations on random access machines, Journal of the ACM (JACM), v.32 n.4, p.929-937, Oct. 1985
	Michael Soss , Jeff Erickson , Mark Overmars, Preprocessing chains for fast dihedral rotations is hard or even impossible, Computational Geometry: Theory and Applications, v.26 n.3, p.235-246, November 2003
	Nir Ailon , Bernard Chazelle, Lower bounds for linear degeneracy testing, Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, June 13-16, 2004, Chicago, IL, USA
	Jun Xu , Richard J. Lipton, On fundamental tradeoffs between delay bounds and computational complexity in packet scheduling algorithms, IEEE/ACM Transactions on Networking (TON), v.13 n.1, p.15-28, February 2005
	David Pisinger, Where are the hard knapsack problems?, Computers and Operations Research, v.32 n.9, p.2271-2284, September 2005
	Nir Ailon , Bernard Chazelle, Lower bounds for linear degeneracy testing, Journal of the ACM (JACM), v.52 n.2, p.157-171, March 2005
	Mihai Prunescu, Two situations with unit-cost: ordered abelian semi-groups and some commutative rings, Journal of Complexity, v.21 n.4, p.579-592, August 2005
	Pierre Charbit , Emmanuel Jeandel , Pascal Koiran , Sylvain Perifel , Stéphan Thomassé, Finding a vector orthogonal to roughly half a collection of vectors, Journal of Complexity, v.24 n.1, p.39-53, February, 2008