Portal de Periódicos da CAPES

Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems

1998; Society for Industrial and Applied Mathematics; Volume: 27; Issue: 5 Linguagem: Inglês

10.1137/s0097539795285254

1095-7111

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

Formal Methods in Verification

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].