✦ LIBER ✦

Improved Approximation Algorithms for Uniform Connectivity Problems

✍ Scribed by Samir Khuller; Balaji Raghavachari

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 174 KB
Volume: 21
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1996.0052

No coin nor oath required. For personal study only.

✦ Synopsis

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. The following results are presented:

For the unweighted k-edge-connectivity problem an approximation algorithm that achieves a performance ratio of 1.85 is described. This is the first polynomial-time algorithm that achieves a constant less than 2, for all k.
For the weighted k-vertex-connectivity problem, a constant factor approximation algorithm is given assuming that the edge-weights satisfy the triangle inequality. This is the first constant factor approximation algorithm for this problem.
For the case of biconnectivity, with no assumptions about the weights of the edges, an algorithm that achieves a factor asymptotically approaching 2 is described. This matches the previous best bound for the corresponding edge connectivity problem.

📜 SIMILAR VOLUMES

NOTE Improved Approximation Algorithms f

NOTE Improved Approximation Algorithms for Weighted 2- and 3-Vertex Connectivity Augmentation Problems

✍ Michal Penn; Haya Shasha-Krupnik 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 126 KB

The problem of finding a minimum augmenting edge-set to make a graph k-vertex connected is considered. This problem is denoted as the minimum k-augmentation problem. For weighted graphs, the minimum k-augmentation problem is NP-complete. Our main result is an approximation algorithm with a performan

Approximation Algorithms for Dispersion

Approximation Algorithms for Dispersion Problems

✍ Barun Chandra; Magnús M Halldórsson 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 182 KB

Improved Approximation Algorithms for MA

Improved Approximation Algorithms for MAX SAT

✍ Takao Asano; David P. Williamson 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 215 KB

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 pze

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

Approximation Algorithms for Directed St

Approximation Algorithms for Directed Steiner Problems

✍ Moses Charikar; Chandra Chekuri; To-yat Cheung; Zuo Dai; Ashish Goel; Sudipto Gu 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 181 KB

We give the first non-trivial approximation algorithms for the Steiner tree problem and the generalized Steiner network problem on general directed graphs. These problems have several applications in network design and multicast routing.

A Static 2-Approximation Algorithm for V

A Static 2-Approximation Algorithm for Vertex Connectivity and Incremental Approximation Algorithms for Edge and Vertex Connectivity

✍ Monika Rauch Henzinger 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 329 KB

This paper presents insertions-only algorithms for maintaining the exact andror approximate size of the minimum edge cut and the minimum vertex cut of a graph. Ž . The algorithms output the approximate or exact size k in time O 1 and a cut of size k in time linear in its size. For the minimum edge