A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
From MaRDI portal
Publication:3768396
DOI10.1145/828.322450zbMath0631.68037OpenAlexW2150121468MaRDI QIDQ3768396
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
Related Items (24)
A polynomial-time linear decision tree for the traveling salesman problem and other NP-complete problems ⋮ Generalized Knapsack problems and fixed degree separations ⋮ Two situations with unit-cost: ordered abelian semi-groups and some commutative rings ⋮ Lower bound arguments with ``inaccessible numbers ⋮ Semi-algebraic decision complexity, the real spectrum, and degree ⋮ Rough analysis of computation trees ⋮ A lower bound for randomized algebraic decision trees ⋮ On genuinely time bounded computations ⋮ Subquadratic algorithms for algebraic 3SUM ⋮ A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model ⋮ Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location ⋮ Unnamed Item ⋮ Efficient evaluation of specific queries in constraint databases ⋮ Preprocessing chains for fast dihedral rotations is hard or even impossible. ⋮ Vapnik-Chervonenkis Dimension of Parallel Arithmetic Computations ⋮ Finding a vector orthogonal to roughly half a collection of vectors ⋮ Evaluating geometric queries using few arithmetic operations ⋮ Where are the hard knapsack problems? ⋮ Calculs sur les structures de langage dénombrable ⋮ Lower bounds for arithmetic networks ⋮ Lower bounds for sorting of sums ⋮ Simulating probabilistic by deterministic algebraic computation trees ⋮ Decision trees: Old and new results. ⋮ On 3SUM-hard problems in the decision tree model
This page was built for publication: A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
