Mathematics – Combinatorics
Scientific paper
1994-09-21
Mathematics
Combinatorics
41 pages
Scientific paper
We extend the concept of polynomial time approximation algorithms to apply to problems for hierarchically specified graphs, many of which are PSPACE-complete. Assuming P != PSPACE, the existence or nonexistence of such efficient approximation algorithms is characterized, for several standard graph theoretic and combinatorial problems. We present polynomial time approximation algorithms for several standard PSPACE-hard problems considered in the literature. In contrast, we show that unless P = PSPACE, there is no polynomial time epsilon-approximation for any epsilon>0, for several other problems, when the instances are specified hierarchically. We present polynomial time approximation algorithms for the following problems when the graphs are specified hierarchically: {minimum vertex cover}, {maximum 3SAT}, {weighted max cut}, {minimum maximal matching}, {bounded degree maximum independent set} In contrast, we show that unless P = PSPACE, there is no polynomial time epsilon-approximation for any epsilon>0, for the following problems when the instances are specified hierarchically: {the number of true gates in a monotone acyclic circuit when all input values are specified} and {the optimal value of the objective function of a linear program} It is also shown that unless P = PSPACE, a performance guarantee of less than 2 cannot be obtained in polynomial time for the following problems when the instances are specified hierarchically: {high degree subgraph}, {k-vertex connected subgraph}, and {k-edge connected subgraph}
Hunt III Harry B.
Marathe Madhav V.
Ravi Srivaths
No associations
LandOfFree
The complexity of approximating PSPACE-Complete problems for hierarchical specifications 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 The complexity of approximating PSPACE-Complete problems for hierarchical specifications, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The complexity of approximating PSPACE-Complete problems for hierarchical specifications will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-635598