✦ LIBER ✦

Improved Approximation Algorithms for MAX SAT

✍ Scribed by Takao Asano; David P. Williamson

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 215 KB
Volume: 42
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.2001.1202

No coin nor oath required. For personal study only.

✦ Synopsis

MAX SAT (the maximum s~tisfiability problem) is stated as follows: given a set of clauses with weights, find a truth assignment that maximizes the sum of the weights of the satisfied clauses. In this paper, we consider approxima~ tion algorithms for MAX SAT proposed by Goemans and Williamson and pzesent a sharpened analysis of their pezfozmance guarantees. We also show that these algorithms, combined with recent approximation algorithms for MAX 2SAT, MAX 3SAT, and MAX SAT due to Feige and Goeroans, Karloff and Zwick, and Zwick, respectively, lead to an improved appzoxiination algorithm for MAX SAT. By using the MAX 2SAT and 3SAT algorithms, we obtain a performance guarantee of .7846, and by using Zwick's algorithm, we obtain a perfozmance guarantee of .8331, which improves upon the perfozmance guazantee of .7977 based on Zwick's conjecture. The best previous result for MAX SAT without assuming Zwick's conjectuze is a .770-appzoximation algorithm of Asano. Our best algorithm requires a new family of 3/4--approximation algorithms that generalize a previous algorithm of Goemans and Williamson.

📜 SIMILAR VOLUMES

On Approximation Algorithms for Hierarch

On Approximation Algorithms for Hierarchical MAX-SAT

✍ Sameet Agarwal; Anne Condon 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 232 KB

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

Approximation Algorithms for MAX 4-SAT a

Approximation Algorithms for MAX 4-SAT and Rounding Procedures for Semidefinite Programs

✍ Eran Halperin; Uri Zwick 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 188 KB

Karloff and Zwick obtained recently an optimal 7r8-approximation algorithm for MAX 3-SAT. In an attempt to see whether similar methods can be used to obtain a 7r8-approximation algorithm for MAX SAT, we consider the most natural generalization of MAX 3-SAT, namely MAX 4-SAT. We present a semidefinit

Approximation Algorithms for Min–Max Tre

Approximation Algorithms for Min–Max Tree Partition

✍ Nili Guttmann-Beck; Refael Hassin 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 298 KB

We consider the problem of partitioning the node set of a graph into p equal sized subsets. The objective is to minimize the maximum length, over these subsets, of a minimum spanning tree. We show that no polynomial algorithm with bounded Ž 2 . error ratio can be given for the problem unless P s NP.

Improved Approximation Algorithms for Tr

Improved Approximation Algorithms for Tree Alignment

✍ Lusheng Wang; Dan Gusfield 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 251 KB

Multiple sequence alignment is a task at the heart of much of current computaw x tional biology 4 . Several different objective functions have been proposed to formalize the task of multiple sequence alignment, but efficient algorithms are lacking in each case. Thus multiple sequence alignment is on

Improved Approximation Algorithms for Un

Improved Approximation Algorithms for Uniform Connectivity Problems

✍ Samir Khuller; Balaji Raghavachari 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 174 KB

The problem of finding minimum-weight spanning subgraphs with a given connectivity requirement is considered. The problem is NP-hard when the connectivity requirement is greater than one. Polynomial time approximation algorithms for various weighted and unweighted connectivity problems are given. Th

An Improved Approximation Algorithm for

An Improved Approximation Algorithm for MULTIWAY CUT

✍ Gruia Călinescu; Howard Karloff; Yuval Rabani 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 132 KB

Given an undirected graph with edge costs and a subset of k nodes called terminals, a multiway cut is a subset of edges whose removal disconnects each terminal from the rest. Multiway Cut is the problem of finding a multiway cut of minimum cost. Previously, a very simple combinatorial algorithm due