Approximating linear programming is log-space complete for P
From MaRDI portal
Publication:750289
DOI10.1016/0020-0190(91)90194-MzbMath0713.90046OpenAlexW2029091075MaRDI QIDQ750289
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
Analysis of algorithms and problem complexity (68Q25) Abstract computational complexity for mathematical programming problems (90C60) Linear programming (90C05)
Related Items
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