The complexity of linear programming in ( , )-form

DOI10.1016/J.IPL.2007.08.025MaRDI QIDQ2380073zbMATH OpenOpenAlexFDO

Authors Pavlos S. Efraimidis

Publication date 24 March 2010

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

Full work available at URL https://doi.org/10.1016/j.ipl.2007.08.025

zbMATH Keywords

computational complexityanalysis of algorithmsapproximation algorithms

Mathematics Subject Classification ID

Linear programming (90C05) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Recommendations

• Approximating linear programming is log-space complete for P
• On the space complexity of linear programming with preprocessing
• Linear Programming in O([n3/ln n]L) Operations
• A note on approximate linear programming
• LP relaxations of some NP-hard problems are as hard as any LP

Cites work

• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• A parallel approximation algorithm for positive linear programming
• A sublinear-time randomized approximation algorithm for matrix games
• Erratum: A correction to Parallel approximation algorithms by positive linear programming
• Parallel approximation algorithms by positive linear programming

Cited in

(3)

• On the complexity of linear programming in the BSS-model
• Approximating linear programming is log-space complete for P
• A note on approximate linear programming

This page was built for publication: The complexity of linear programming in \((\gamma ,\kappa )\)-form

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