A Simplified Analysis of the Good-Bad $3/2$-Approximation Algorithm for Some Minimum-Cost Graph Problems

Shayan Ranjbarzadeh, David P. Williamson, Hannane Yaghoubizade

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…