NDLI: Tight Results on Minimum Entropy Set Cover

Content Provider	Springer Nature Link
Author	Cardinal, Jean Fiorini, Samuel Joret, Gwenaël
Copyright Year	2007
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.
Starting Page	49
Ending Page	60
Page Count	12
File Format	PDF
ISSN	01784617
Journal	Algorithmica
Volume Number	51
Issue Number	1
e-ISSN	14320541
Language	English
Publisher	Springer-Verlag
Publisher Date	2007-10-13
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Entropy Greedy algorithm Hardness of approximation Set cover Data Structures, Cryptology and Information Theory Computer Systems Organization and Communication Networks Algorithms Mathematics of Computing Theory of Computation Algorithm Analysis and Problem Complexity
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum k-Way Cut Problem

Multi-rooted Greedy Approximation of Directed Steiner Trees with Applications

An Approximation Algorithm for the Minimum Co-Path Set Problem

Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems

Improved Approximation Algorithms for Label Cover Problems

Randomized Approximation for the Set Multicover Problem in Hypergraphs

Hardness and approximation results for packing steiner trees

Minimum-Perimeter Intersecting Polygons

An Optimal Algorithm for the Minimum Disc Cover Problem

Tight Results on Minimum Entropy Set Cover

Similar Documents

Tight Approximation Ratio of a General Greedy Splitting Algorithm for the Minimum k-Way Cut Problem

Multi-rooted Greedy Approximation of Directed Steiner Trees with Applications

An Approximation Algorithm for the Minimum Co-Path Set Problem

Exact and Approximation Algorithms for Geometric and Capacitated Set Cover Problems

Improved Approximation Algorithms for Label Cover Problems

Randomized Approximation for the Set Multicover Problem in Hypergraphs

Hardness and approximation results for packing steiner trees

Minimum-Perimeter Intersecting Polygons

An Optimal Algorithm for the Minimum Disc Cover Problem

Tight Results on Minimum Entropy Set Cover