Abstract
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 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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Alon, N., Orlitsky, A.: Source coding and graph entropies. IEEE Trans. Inf. Theory 42(5), 1329–1339 (1996)
Cardinal, J., Fiorini, S., Joret, G.: Minimum entropy coloring. In: Proceedings of the 16th International Symposium on Algorithms and Computation (ISAAC 2005). Lecture Notes in Computer Science, vol. 3827, pp. 819–828. Springer, Berlin (2005)
Feige, U.: A threshold of ln n for approximating set cover. J. ACM 45(4), 634–652 (1998)
Feige, U., Kilian, J.: Zero knowledge and the chromatic number. J. Comput. Syst. Sci. 57(2), 187–199 (1998). Complexity 96—The 11th Annual IEEE Conference on Computational Complexity, Philadelphia
Feige, U., Lovász, L., Tetali, P.: Approximating min sum set cover. Algorithmica 40(4), 219–234 (2004)
Feller, W.: An Introduction to Probability Theory and Its Applications. vol. I, 3rd edn. Wiley, New York (1968)
Grötschel, M., Lovász, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Algorithms and Combinatorics, vol. 2, 2nd edn. Springer, Berlin (1993)
Halperin, E., Karp, R.M.: The minimum-entropy set cover problem. Theor. Comput. Sci. 348(2-3), 240–250 (2005)
Hardy, G.H., Littlewood, J.E., Pólya, G.: Inequalities. Cambridge Mathematical Library. Cambridge University Press, Cambridge (1988). Reprint of the 1952 edition
Nakamura, D., Tamura, A.: A revision of Minty’s algorithm for finding a maximum weight stable set of a claw-free graph. J. Oper. Res. Soc. Jpn. 44(2), 194–204 (2001)
Author information
Authors and Affiliations
Corresponding author
Additional information
G. Joret is a Research Fellow of the Fonds National de la Recherche Scientifique (FNRS).
Rights and permissions
About this article
Cite this article
Cardinal, J., Fiorini, S. & Joret, G. Tight Results on Minimum Entropy Set Cover. Algorithmica 51, 49–60 (2008). https://doi.org/10.1007/s00453-007-9076-8
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00453-007-9076-8