On the Space Complexity of Linear Programming with Preprocessing

DOI10.1145/2840728.2840750zbMath1334.68105OpenAlexW2283590027MaRDI QIDQ2800577

Ran Raz, Yael Tauman Kalai, 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

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

Related Items (2)

Unnamed Item ⋮ Unnamed Item

This page was built for publication: On the Space Complexity of Linear Programming with Preprocessing