%0 Journal Article
%T Improved approximation algorithms for low-density instances of the Minimum Entropy Set Cover Problem
%A Cosmin Bonchis
%A Gabriel Istrate
%J Computer Science
%D 2012
%I arXiv
%X We study the approximability of instances of the minimum entropy set cover problem, parameterized by the average frequency of a random element in the covering sets. We analyze an algorithm combining a greedy approach with another one biased towards large sets. The algorithm is controled by the percentage of elements to which we apply the biased approach. The optimal parameter choice has a phase transition around average density $e$ and leads to improved approximation guarantees when average element frequency is less than $e$.
%U http://arxiv.org/abs/1207.7134v1