Lower bounds for parallel linear programming and other problems
From MaRDI portal
Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parallel algorithms in computer science (68W10) Linear programming (90C05) Programming involving graphs or networks (90C35)
Recommendations
- Lower Bounds in a Parallel Model without Bit Operations
- Lower bounds for parallel algebraic decision trees, parallel complexity of convex hulls and related problems
- A Deterministic ${\operatorname{Poly}}(\log \log N)$-TimeN-Processor Algorithm for Linear Programming in Fixed Dimension
- Some lower bounds for the complexity of the linear programming feasibility problem over the reals
- Linear Programming with Two Variables Per Inequality in Poly-Log Time
Cited in
(9)- Nearly sharp complexity bounds for multiprocessor algebraic computations
- Lower bounds for arithmetic networks
- Linear FPT reductions and computational lower bounds
- scientific article; zbMATH DE number 4092792 (Why is no real title available?)
- scientific article; zbMATH DE number 1354139 (Why is no real title available?)
- Lower Bounds in a Parallel Model without Bit Operations
- scientific article; zbMATH DE number 1559536 (Why is no real title available?)
- scientific article; zbMATH DE number 871908 (Why is no real title available?)
- Some lower bounds for the complexity of the linear programming feasibility problem over the reals
This page was built for publication: Lower bounds for parallel linear programming and other problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2817655)
