The complexity of linear programming in ( , )-form

DOI10.1016/J.IPL.2007.08.025zbMATH Open1191.68863OpenAlexW2058105169MaRDI QIDQ2380073FDOQ2380073

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

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

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)

Cites Work

• A sublinear-time randomized approximation algorithm for matrix games
• Title not available (Why is that?)
• A parallel approximation algorithm for positive linear programming
• 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)