Computer Science – Computational Complexity
Scientific paper
1998-09-23
SIAM J. Computing, Vol. 27, No 5, Oct. 1998, pp. 1237--1261
Computer Science
Computational Complexity
5 Figures, 24 pages
Scientific paper
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}.
Hunt III Harry B.
Marathe Madhav V.
Radhakrishnan Venkatesh
Stearns Richard E.
No associations
LandOfFree
Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Approximation Algorithms for PSPACE-Hard Hierarchically and Periodically Specified Problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-194302