Approximation schemes for PSPACE-complete problems for succinct specifications (preliminary version)

DOI10.1145/195058.195233zbMath1345.68276OpenAlexW2008232159MaRDI QIDQ2817638

Venkatesh Radhakrishnan, Richard E. Stearns, Harry B. III Hunt, Madhav V. Marathe

Publication date: 1 September 2016

Published in: Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (2)

A nonapproximability result for finite function generation ⋮ Hierarchically specified unit disk graphs

This page was built for publication: Approximation schemes for PSPACE-complete problems for succinct specifications (preliminary version)