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

Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25) 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

• 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?)
• A new polynomial-time algorithm for linear programming
• A taxonomy of problems with fast parallel algorithms
• Linear programming is log-space hard for P
• The complexity of linear programming

Cited in

(20)

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

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)