On Approximation Algorithms for Hierarchical MAX-SAT

✍ Scribed by Sameet Agarwal; Anne Condon

• Publisher: Elsevier Science
• Year: 1998
• Tongue: English
• Weight: 232 KB
• Volume: 26
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.1997.0902

✦ Synopsis

We prove upper and lower bounds on performance guarantees of approximation Ž . algorithms for the hierarchical MAX-SAT H-MAX-SAT problem. This problem is representative of a broad class of PSPACE-hard problems involving graphs, Boolean formulas, and other structures that are defined succinctly.

Our first result is that, for some constant ⑀ -1, it is PSPACE-hard to approximate the function H-MAX-SAT to within ratio ⑀. We obtain our result using a reduction from the language recognition problem for a model of PSPACE called the probabilistically checkable debate system. As an immediate application, we obtain nonapproximability results for functions on hierarchical graphs by combining our result with previously known approximation-preserving reductions to other problems. For example, it is PSPACE-hard to approximate H-MAX-CUT and H-MAX-INDEPENDENT-SET to within some constant factor.

Our second result is that there is an efficient approximation algorithm for H-MAX-SAT with performance guarantee 2r3. The previous best bound claimed for this problem was 1r2. One new technique of our algorithm can be used to obtain approximation algorithms for other problems, such as hierarchical MAX-CUT, which are simpler than previously known algorithms and which have performance guarantees that match the previous best bounds.