A Polynomial Linear Search Algorithm for the n -Dimensional Knapsack Problem
From MaRDI portal
Publication:3768396
Recommendations
Cited in
(25)- Decomposing arrangements of hyperplanes: VC-dimension, combinatorial dimension, and point location
- 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
- A nearly quadratic bound for point-location in hyperplane arrangements, in the linear decision tree model
- Semi-algebraic decision complexity, the real spectrum, and degree
- Pseudo-polynomial algorithms for solving the knapsack problem with dependencies between items
- On genuinely time bounded computations
- 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
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)
