Recursive Greedy Methods
Guy Even · 2018
Greedy algorithms are often the first algorithm that one considers for various optimization problems, and, in particular, covering problems. The idea is very simple: try to build a solution incrementally by augmenting a partial solution. In each iteration, select the "best" augmentation according to a simple criterion. The term greedy is used because the most common criterion is to select an augmentation that minimizes the ratio of "cost" to "advantage." The chapter reviews the greedy algorithm for the Set-Cover (SC) problem and its analysis. It also presents a recursive greedy algorithm for the l-shallow k-DST problem. Based on the layering transformation, the chapter suggests that the input graph is an l-layered acyclic directed graph. The algorithm is designed for problems in which finding a minimum density augmentation of a partial solution is an NP-hard problem.