scientific article; zbMATH DE number 1559524

MaRDI QIDQ4526972zbMATH OpenFDO

Authors Dima Grigoriev, Marek Karpinski

Publication date 28 February 2001

zbMATH Keywords

knapsack problemrandomized computation trees

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 1775407
• scientific article; zbMATH DE number 1256781
• Complexity lower bounds for randomized computation trees over zero characteristic fields
• scientific article; zbMATH DE number 2032368
• A lower bound for randomized algebraic decision trees

Cited in

(11)

• Randomized complexity lower bound for arrangements and polyhedra
• Complexity lower bounds for randomized computation trees over zero characteristic fields
• An alternative to Ben-Or's lower bound for the knapsack problem complexity
• RANDOMIZATION YIELDS SIMPLE O(n log^⋆ n) ALGORITHMS FOR DIFFICULT Ω(n) PROBLEMS
• scientific article; zbMATH DE number 1775407 (Why is no real title available?)
• Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions
• scientific article; zbMATH DE number 3999287 (Why is no real title available?)
• The Lower Bound for Koldobsky’s Slicing Inequality via Random Rounding
• Random knapsack in expected polynomial time
• Complexity of Positivstellensatz proofs for the knapsack
• On exponential time lower bound of Knapsack under backtracking

This page was built for publication:

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