Ad Astra Awards
Ad Astra Journal
Science library
White book
University rankings
Who's who
Publications
Theses and dissertations
Ad Astra association
 
Press releases
News
Events
Funding opportunities
 
Login
Registration
 
>> Românã
 
   
 

Gabriel Istrate, Cosmin Bonchis, Liviu P. Dinu. The Minimum Entropy Submodular Set Cover Problem . In Proceedings of the 10th International Conference on Language and Automata Theory and Applications (LATA' 2016), pp. 295-306. Lecture Notes in Computer Science, vol. 9618, Springer Verlag , 2016.

Abstract: We study minimum entropy submodular set cover, a variant of the submodular set cover problem (Wolsey, Fujito, etc) that generalizes the minimum entropy set cover problem (Halperin and Karp, Cardinal et al.)

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) a worst-case approach to fairness in concave cooperative games.

Keywords: submodular optimization, minimum entropy

URL: http://link.springer.com/chapter/10.1007/978-3-319-30000-9_23

Posted by Gabriel Istrate

Back

   
© Ad Astra 2001-2013