Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems
<|reference_start|>Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems: We 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 $\Pi$ considered when specified using {\bf k-level-restricted} hierarchical specifications or $k$-narrow periodic specifications the following holds:   \item Let $\rho$ be any performance guarantee of a polynomial time approximation algorithm for $\Pi$, when instances are specified using standard specifications. Then $\forall \epsilon > 0$, $ \Pi$ has a polynomial time approximation algorithm with performance guarantee $(1 + \epsilon) \rho$. \item $\Pi$ 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}.<|reference_end|>
@article{marathe1998approximation,
    title={Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically
  Specified Problems},
    author={Madhav V. Marathe, Harry B. Hunt III, Richard E. Stearns, Venkatesh
  Radhakrishnan},
    journal={SIAM J. Computing, Vol. 27, No 5, Oct. 1998, pp. 1237--1261},
    year={1998},
    archivePrefix={arXiv},
    eprint={cs/9809064},
    primaryClass={cs.CC cs.DS}
}