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

DOI10.1137/0219068zbMATH Open0711.68063OpenAlexW2085048392MaRDI QIDQ3495656FDOQ3495656

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

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

zbMATH Keywords

linear programmingparallel computationtime complexitypoly-log time

Mathematics Subject Classification ID

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

Cited In (8)

• Solving related two- and three-dimensional linear programming problems in logarithmic time
• Two-variable linear programming in parallel
• Linear Time Algorithms for Two- and Three-Variable Linear Programs
• Improved Algorithms For Linear Inequalities with Two Variables Per Inequality
• Title not available (Why is that?)
• Two-variable linear programming in parallel
• An \(O(n^ 2)\) simplex algorithm for a class of linear programs with tree structure
• Parallel linear programming in fixed dimension almost surely in constant time

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)