On the space complexity of linear programming with preprocessing

DOI10.1145/2840728.2840750zbMATH Open1334.68105OpenAlexW2283590027MaRDI QIDQ2800577FDOQ2800577

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

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

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)

Cited In (5)

• Title not available (Why is that?)
• 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)