Inscriere cercetatori

Daca aveti cont Ad Astra si de Facebook, intrati pe pagina de profil pentru a da dreptul sa va logati pe site doar cu acest buton.

Site nou !

Daca nu va puteti recupera parola (sau aveti alte probleme), scrieti-ne la pagina de contact. Situl vechi se gaseste la adresa


The Minimum Entropy Submodular Set Cover Problem

Autori: Gabriel Istrate, Cosmin Bonchis, Liviu P. Dinu

Editorial: Proceedings of the 10th International Conference on Language and Automata Theory and Applications (LATA' 2016), Lecture Notes in Computer Science vol. 9618, p.295-306, Springer Verlag, 2016.


Want create site? Find Free WordPress Themes and plugins.

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.

Did you find apk for android? You can find new Free Android Games and apps.