On the space complexity of linear programming with preprocessing

DOI10.1145/2840728.2840750MaRDI QIDQ2800577zbMATH OpenOpenAlexFDO

Authors Yael Tauman Kalai, Ran Raz, Oded Regev

Publication date 15 April 2016

Published in Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2840728.2840750

zbMATH Keywords

linear programmingspace complexitypreprocessingP-completeness

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
• A note on approximate linear programming
• LP relaxations of some NP-hard problems are as hard as any LP
• The complexity of approximating a nonlinear program
• scientific article; zbMATH DE number 1182931

Cited in

(5)

• scientific article; zbMATH DE number 7250157 (Why is no real title available?)
• Probabilistic checking against non-signaling strategies from linearity testing
• The complexity of linear programming in \((\gamma ,\kappa )\)-form
• Approximating linear programming is log-space complete for P
• A note on approximate linear programming

This page was built for publication: On the space complexity of linear programming with preprocessing

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