Randomized complexity of linear arrangements and polyhedra

DOI10.1007/3-540-48321-7_1MaRDI QIDQ4934316zbMATH OpenFDO

Authors Marek Karpinski

Publication date 17 January 2000

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-48321-7_1

zbMATH Keywords

bounded integer programmingknapsack

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Recommendations

• Randomized complexity lower bound for arrangements and polyhedra
• Small-dimensional linear programming and convex hulls made easy
• scientific article; zbMATH DE number 1775407
• scientific article; zbMATH DE number 1256781
• A lower bound for randomized algebraic decision trees

Cited in

(5)

• Polymatroids: Construction and random algorithms
• Randomized complexity lower bound for arrangements and polyhedra
• Complexity lower bounds for randomized computation trees over zero characteristic fields
• Randomized construction of complexes with large diameter
• Complexity analysis of random geometric structures made simpler

This page was built for publication: Randomized complexity of linear arrangements and polyhedra

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