Name
Abstract | ||
|---|---|---|
We study Minimum Entropy Submodular Set Cover, a variant of the Submodular Set Cover problem (Wolsey [21], Fujito [8], etc.) that generalizes the Minimum Entropy Set Cover problem (Halperin and Karp [11], Cardinal et al. [4]) We give a general bound on the approximation performance of the greedy algorithm using an approach that can be interpreted in terms of a particular type of biased network flows. As an application we rederive known results for the Minimum Entropy Set Cover and Minimum Entropy Orientation problems, and obtain a nontrivial bound for a new problem called the Minimum Entropy Spanning Tree problem. The problem can be applied to (and is partly motivated by) a worst-case approach to fairness in concave cooperative games. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/978-3-319-30000-9_23 | Lecture Notes in Computer Science |
Keywords | Field | DocType |
Submodular set cover,Minimum entropy,Approximation algorithms | Flow network,Set cover problem,Approximation algorithm,Discrete mathematics,Combinatorics,Minimum entropy,Computer science,Submodular set function,Greedy algorithm,Spanning tree | Conference |
Volume | ISSN | Citations |
9618 | 0302-9743 | 1 |
PageRank | References | Authors |
0.39 | 9 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Gabriel Istrate | 1 | 99 | 24.96 |
| Cosmin Bonchiş | 2 | 13 | 7.75 |
| Liviu P. Dinu | 3 | 164 | 35.89 |