Greed is good: approximating independent sets in sparse and bounded-degree graphs

Halldórsson, M. M. ; Radhakrishnan, J. (1997) Greed is good: approximating independent sets in sparse and bounded-degree graphs Algorithmica, 18 (1). pp. 145-163. ISSN 0178-4617

Full text not available from this repository.

Official URL: http://www.springerlink.com/index/557J2MFNA23YXJLV...

Related URL: http://dx.doi.org/10.1007/BF02523693

Abstract

The minimum-degree Greedy algorithm, or Greedy for short, is one of the simplest, most efficient, and most thoroughly studied methods for finding independent sets in graphs. We show that it surprisingly achieves a performance ratio of (Δ + 2)=3 for approximating independent sets in graphs with degree bounded by Δ. The analysis directs us towards a simple parallel and distributed algorithm with identical performance, which on constant-degree graphs runs in O(log n) time using linear number of processors. We also analyze the Greedy algorithm when run in combination with a fractional relaxation technique of Nemhauser and Trotter, and obtain an improved (2d̅ + 3)=5 performance ratio on graphs with average degree ̅. Finally, we introduce a generally applicable technique for improving the approximation ratios of independent set algorithms, and illustrate it by improving the performance ratio of Greedy for large Δ.

Item Type:Article
Source:Copyright of this article belongs to Springer.
Keywords:Independent Set Problem; Heuristics; Approximation Algorithms
ID Code:89522
Deposited On:27 Apr 2012 13:35
Last Modified:27 Apr 2012 13:35

Repository Staff Only: item control page