A note on approximate linear programming

DOI10.1016/0020-0190(92)90132-FzbMath0762.90051OpenAlexW2072883586MaRDI QIDQ1198023

Nimrod Megiddo

Publication date: 16 January 1993

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(92)90132-f

zbMATH Keywords

approximate solution\(P\)-complete

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05)

Related Items

Parallel approximation of min-max problems ⋮ A subexponential bound for linear programming

Cites Work

• Approximating linear programming is log-space complete for P
• Unnamed Item