| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 4652765 | Electronic Notes in Discrete Mathematics | 2010 | 7 Pages |
Abstract
We define a NP-hard clustered variant of the Set Covering Problem where subsets are partitioned into K clusters and a fixed cost is paid for selecting at least one subset in a given cluster. This variant can reformulate as a master problem various multi-commodity flow problems in transportation planning. We show that the problem is approximable within ratio (1+ϵ)(e/e−1)H(q), where q is the maximum number of elements covered by a cluster and .
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
