A Simplified Analysis of the Good-Bad $3/2$-Approximation Algorithm for Some Minimum-Cost Graph Problems
Data Structures and AlgorithmsDiscrete Mathematics
Summary
The authors study a simple greedy algorithm called the good-bad algorithm, originally introduced by Couëtoux, which finds a low-cost set of edges ensuring every connected group of nodes has at least k vertices. Couëtoux showed this algorithm gives a solution close to the best possible. Davis and Williamson expanded this method to a broader class of problems involving special sets of nodes defined by a function that is stable under taking smaller subsets. In this paper, the authors provide a clearer and simpler explanation of why the good-bad algorithm works well in this more general setting.
Authors
Shayan Ranjbarzadeh, David P. Williamson, Hannane Yaghoubizade
Abstract
In this paper, we consider an easy greedy approximation algorithm, the good-bad algorithm, introduced by Couëtoux for finding a minimum-cost set of edges such that every connected component has at least $k$ vertices. Couëtoux proves that the good-bad algorithm achieves a $3/2$-approximation for this problem. Davis and Williamson extend this result to the more general problem of finding a minimum-cost edge set that contains at least one edge from every cut $S\subseteq V$ satisfying $h(S) = 1$ where $h:2^V \rightarrow \{0,1\}$ is downward monotone; that is, $h(S) = 1$ implies $h(T) = 1$ for every nonempty subset $T \subseteq S$. The original problem corresponds to $h(S) =1$ when $|S|<k$. We give a simplified analysis of the good-bad algorithm for downward monotone functions.