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

DOI10.1145/828.322450zbMATH Open0631.68037OpenAlexW2150121468MaRDI QIDQ3768396FDOQ3768396

Authors: Friedhelm Meyer auf der Heide 

Publication date: 1984

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/828.322450

Recommendations

• An O(n) algorithm for the multiple-choice knapsack linear program
• scientific article; zbMATH DE number 3852791
• scientific article; zbMATH DE number 1264415
• An O(n) algorithm for the linear multiple choice knapsack problem and related problems
• scientific article; zbMATH DE number 4023019

zbMATH Keywords

NP-completenesslinear search algorithmn-dimensional knapsack problem

Mathematics Subject Classification ID

Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25)

Cited In (25)

• Decision trees: Old and new results.
• A polynomial-time linear decision tree for the traveling salesman problem and other NP-complete problems
• Subquadratic algorithms for algebraic 3SUM
• Evaluating geometric queries using few arithmetic operations
• Lower bound arguments with ``inaccessible numbers
• Calculs sur les structures de langage dénombrable
• Where are the hard knapsack problems?
• Efficient evaluation of specific queries in constraint databases
• Pseudo-polynomial algorithms for solving the knapsack problem with dependencies between items
• A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model
• On genuinely time bounded computations
• Semi-algebraic decision complexity, the real spectrum, and degree
• Finding a vector orthogonal to roughly half a collection of vectors
• Generalized Knapsack problems and fixed degree separations
• Vapnik-Chervonenkis Dimension of Parallel Arithmetic Computations
• Two situations with unit-cost: ordered abelian semi-groups and some commutative rings
• Rough analysis of computation trees
• Preprocessing chains for fast dihedral rotations is hard or even impossible.
• Generalized comparison trees for point-location problems
• Lower bounds for sorting of sums
• Lower bounds for arithmetic networks
• A lower bound for randomized algebraic decision trees
• Simulating probabilistic by deterministic algebraic computation trees
• On 3SUM-hard problems in the decision tree model
• Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location

This page was built for publication: A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3768396)