Approximating linear programming is log-space complete for P

DOI10.1016/0020-0190(91)90194-MzbMath0713.90046OpenAlexW2029091075MaRDI QIDQ750289

Maria J. Serna

Publication date: 1991

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

Full work available at URL: https://doi.org/10.1016/0020-0190(91)90194-m

zbMATH Keywords

approximationsBoolean circuitP-complete under log-space reductions

Mathematics Subject Classification ID

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

Related Items (14)

On the Average Case Complexity of Some P-complete Problems ⋮ Parallel approximation of min-max problems ⋮ Complexity results for preference aggregation over \((m)\)CP-nets: max and rank voting ⋮ Parallel approximation schemes for problems on planar graphs ⋮ On parallel versus sequential approximation ⋮ Parallel approximation to high multiplicity scheduling problemsVIAsmooth multi-valued quadratic programming ⋮ Sublinear-space approximation algorithms for Max \(r\)-SAT ⋮ The complexity of approximating PSPACE-complete problems for hierarchical specifications ⋮ A note on approximate linear programming ⋮ Approximating the minimum-cost maximum flow is P-complete ⋮ On the parallel approximability of a subclass of quadratic programming. ⋮ Approximation in (Poly-) logarithmic space ⋮ Approximation in (Poly-) Logarithmic Space ⋮ Solving LP Relaxations of Some NP-Hard Problems Is As Hard As Solving Any Linear Program

Cites Work

• A new polynomial-time algorithm for linear programming
• Linear programming is log-space hard for P
• A taxonomy of problems with fast parallel algorithms
• The complexity of linear programming
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Approximating linear programming is log-space complete for P