Computer Science – Data Structures and Algorithms
Scientific paper
2008-02-15
Computer Science
Data Structures and Algorithms
14 pages, 1 figure
Scientific paper
We introduce a parameterized version of set cover that generalizes several previously studied problems. Given a ground set V and a collection of subsets S_i of V, a feasible solution is a partition of V such that each subset of the partition is included in one of the S_i. The problem involves maximizing the mean subset size of the partition, where the mean is the generalized mean of parameter p, taken over the elements. For p=-1, the problem is equivalent to the classical minimum set cover problem. For p=0, it is equivalent to the minimum entropy set cover problem, introduced by Halperin and Karp. For p=1, the problem includes the maximum-edge clique partition problem as a special case. We prove that the greedy algorithm simultaneously approximates the problem within a factor of (p+1)^1/p for any p in R^+, and that this is the best possible unless P=NP. These results both generalize and simplify previous results for special cases. We also consider the corresponding graph coloring problem, and prove several tractability and inapproximability results. Finally, we consider a further generalization of the set cover problem in which we aim at minimizing the sum of some concave function of the part sizes. As an application, we derive an approximation ratio for a Rent-or-Buy set cover problem.
Cardinal Jean
Dumeunier Christophe
No associations
LandOfFree
Set Covering Problems with General Objective Functions does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Set Covering Problems with General Objective Functions, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Set Covering Problems with General Objective Functions will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-38444