Approximation Algorithms for Union and Intersection Covering Problems

Marek Cygan, Fabrizio Grandoni, Stefano Leonardi +3

In a classical covering problem, we are given a set of requests that we need to satisfy (fully or partially), by buying a subset of items at minimum cost. For example, in the k-MST…