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