Approximating linear programming is log-space complete for P

DOI10.1016/0020-0190(91)90194-MMaRDI QIDQ750289zbMATH OpenOpenAlexFDO

Authors Maria 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) Linear programming (90C05) Abstract computational complexity for mathematical programming problems (90C60)

Recommendations

• A note on approximate linear programming
• Linear Programming in O([n3/ln n]L) Operations
• On the space complexity of linear programming with preprocessing
• The complexity of linear programming in \((\gamma ,\kappa )\)-form
• Positive linear programming, parallel approximation and PCP's

Cites work

• A new polynomial-time algorithm for linear programming
• A taxonomy of problems with fast parallel algorithms
• scientific article; zbMATH DE number 4155879 (Why is no real title available?)
• scientific article; zbMATH DE number 4062587 (Why is no real title available?)
• scientific article; zbMATH DE number 3466805 (Why is no real title available?)
• scientific article; zbMATH DE number 3637614 (Why is no real title available?)
• Linear programming is log-space hard for P
• The complexity of linear programming

Cited in

(22)

• A note on approximate linear programming
• Approximating the minimum-cost maximum flow is P-complete
• Parallel approximation schemes for problems on planar graphs
• Approximation in (poly-) logarithmic space
• A note on the approximability of deepest-descent circuit steps
• The complexity of linear programming in \((\gamma ,\kappa )\)-form
• On approximating the eigenvalues of stochastic matrices in probabilistic logspace
• Logspace optimization problems and their approximability properties
• Complexity results for preference aggregation over \((m)\)CP-nets: max and rank voting
• Sublinear-space approximation algorithms for Max r-SAT
• On the space complexity of linear programming with preprocessing
• Parallel approximation to high multiplicity scheduling problemsVIAsmooth multi-valued quadratic programming
• Parallel approximation of min-max problems
• On the Shortest Linear Straight-Line Program for Computing Linear Forms
• On the Average Case Complexity of Some P-complete Problems
• The complexity of approximating \(\mathrm{PSPACE}\)-complete problems for hierarchical specifications
• Approximation in (Poly-) Logarithmic Space
• Solving LP relaxations of some NP-hard problems is as hard as solving any linear program
• Fundamentals of Computation Theory
• On the parallel approximability of a subclass of quadratic programming.
• On parallel versus sequential approximation
• Is the space complexity of planted clique recovery the same as that of detection?

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

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