Linear Programming with Two Variables Per Inequality in Poly-Log Time

DOI10.1137/0219068MaRDI QIDQ3495656zbMATH OpenOpenAlexFDO

Authors George S. Lueker, Nimrod Megiddo, Vijaya Ramachandran

Publication date 1990

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.5834

zbMATH Keywords

linear programmingparallel computationpoly-log timetime complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05)

Recommendations

• A Deterministic ${\operatorname{Poly}}(\log \log N)$-TimeN-Processor Algorithm for Linear Programming in Fixed Dimension
• Linear Time Algorithms for Two- and Three-Variable Linear Programs
• Two-variable linear programming in parallel
• Two-variable linear programming in parallel
• Parallel linear programming in fixed dimension almost surely in constant time

Cited in

(9)

• An O(n^ 2) simplex algorithm for a class of linear programs with tree structure
• Solving related two- and three-dimensional linear programming problems in logarithmic time
• Lower bounds for parallel linear programming and other problems
• Linear Time Algorithms for Two- and Three-Variable Linear Programs
• Parallel linear programming in fixed dimension almost surely in constant time
• Improved Algorithms For Linear Inequalities with Two Variables Per Inequality
• scientific article; zbMATH DE number 6823767 (Why is no real title available?)
• Two-variable linear programming in parallel
• Two-variable linear programming in parallel

This page was built for publication: Linear Programming with Two Variables Per Inequality in Poly-Log Time

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