Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems
MADHAV V. MARATHE, Harry B. Hunt, Richard Edwin Stearns, Venkatesh Radhakrishnan · SIAM Journal on Computing · 1998
We study the efficient approximability of basic graph and logic problems in the literature when instances are specified hierarchically as in [T. Lengauer, J. Assoc. Comput. Mach., 36(1989), pp. 474--509] or are specified by one-dimensional finite narrow periodic specifications as in [E. Wanke, Paths and cycles in finite periodic graphs, in Lecture Notes in Comp. Sci. 711, Springer-Verlag, New York, 1993, pp. 751--760]. We show that, for most of the problems $\Pi$ considered when specified using k-level-restricted hierarchical specifications or k-narrow periodic specifications, the following hold. 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$. $\Pi$ has a polynomial time approximation scheme when restricted to planar instances. 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. [Chicago J. Theoret. Comput. Sci., 1995, Article 4].