Gwenaël Joret (Université Libre de Bruxelles): Tight
results on minimum entropy set cover
In the minimum entropy set cover problem, one is given
a collection of k sets which collectively cover an
n-element ground set. A feasible solution of the problem
is a partition of the ground set into parts such that
each part is included in some of the k given sets. Such
a partition defines a probability distribution, obtained
by dividing each part size by n. The goal is to find
a feasible solution minimizing the (binary) entropy of
the corresponding distribution. Halperin and Karp have
recently proved that the greedy algorithm always returns
a solution whose cost is at most the optimum plus a
constant. We improve their result by showing that the
greedy algorithm approximates the minimum entropy set
cover problem within an additive error of log_2 e bits
(approx. 1.4427 bits). Moreover, inspired by recent work
by Feige, Lovasz and Tetali on the minimum sum set cover
problem, we prove that no polynomial-time algorithm can
achieve a better constant, unless P=NP.