Anzeige
Erschienen in:
2006 | OriginalPaper | Buchkapitel
Tight Results on Minimum Entropy Set Cover
verfasst von : Jean Cardinal, Samuel Fiorini, Gwenaël Joret
Erschienen in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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. The goal is to find a partition minimizing the (binary) entropy of the corresponding probability distribution, i.e., the one found by dividing each part size by
n
. 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 1 nat = log
2
e
bits ≃ 1.4427 bits. Moreover, inspired by recent work by Feige, Lovász and Tetali on the minimum sum set cover problem, we prove that no polynomial-time algorithm can achieve a better constant, unless P = NP. We also discuss some consequences for the related minimum entropy coloring problem.