On the space complexity of linear programming with preprocessing

DOI10.1145/2840728.2840750zbMATH Open1334.68105OpenAlexW2283590027MaRDI QIDQ2800577FDOQ2800577

Ran Raz, Oded Regev, Yael Tauman Kalai

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)

Cited In (3)

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