Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems

Simple item page
dc.creatorMarathe, Madhav V.
dc.creatorHunt III, Harry B.
dc.creatorStearns, Richard E.
dc.creatorRadhakrishnan, Venkatesh
dc.date1998-09-23
dc.date.accessioned2026-07-07T03:23:36Z
dc.date.available2026-07-07T03:23:36Z
dc.descriptionWe study the efficient approximability of basic graph and logic problems in the literature when instances are specified hierarchically as in \cite{Le89} or are specified by 1-dimensional finite narrow periodic specifications as in \cite{Wa93}. We show that, for most of the problems $Π$ considered when specified using {\bf k-level-restricted} hierarchical specifications or $k$-narrow periodic specifications the following holds: \item Let $ρ$ be any performance guarantee of a polynomial time approximation algorithm for $Π$, when instances are specified using standard specifications. Then $\forall ε> 0$, $ Π$ has a polynomial time approximation algorithm with performance guarantee $(1 + ε) ρ$. \item $Π$ has a polynomial time approximation scheme when restricted to planar instances. \end{romannum} These are the first polynomial time approximation schemes for PSPACE-hard hierarchically or periodically specified problems. Since several of the problems considered are PSPACE-hard, our results provide the first examples of natural PSPACE-hard optimization problems that have polynomial time approximation schemes. This answers an open question in Condon et. al. \cite{CF+93}.
dc.description5 Figures, 24 pages
dc.identifierhttps://arxiv.org/abs/cs/9809064
dc.identifierhttp://arxiv.org/abs/cs/9809064
dc.identifierSIAM J. Computing, Vol. 27, No 5, Oct. 1998, pp. 1237--1261
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/33005
dc.subjectComputational Complexity
dc.subjectData Structures and Algorithms
dc.subjectF.1.3; F.2.2
dc.titleApproximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems
dc.typetext

Files

Collections

arXiv