Minimum Entropy Submodular Optimization (and Fairness in Cooperative   Games)
  We study minimum entropy submodular optimization, a common generalization of the minimum entropy set cover problem, studied earlier by Cardinal et al., and the submodular set cover problem.   We give a general bound of 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) the definition of worst-case approaches to fairness in concave cooperative games, similar to the notion of price of anarchy in noncooperative settings. 
Cosmin Bonchi\c{s} and Gabriel Istrate
cs.DS cs.GT math.CO