%0 Journal Article
%T Minimum Entropy Orientations
%A Jean Cardinal
%A Samuel Fiorini
%A Gwena£żl Joret
%J Computer Science
%D 2008
%I arXiv
%R 10.1016/j.orl.2008.06.010
%X We study graph orientations that minimize the entropy of the in-degree sequence. The problem of finding such an orientation is an interesting special case of the minimum entropy set cover problem previously studied by Halperin and Karp [Theoret. Comput. Sci., 2005] and by the current authors [Algorithmica, to appear]. We prove that the minimum entropy orientation problem is NP-hard even if the graph is planar, and that there exists a simple linear-time algorithm that returns an approximate solution with an additive error guarantee of 1 bit. This improves on the only previously known algorithm which has an additive error guarantee of log_2 e bits (approx. 1.4427 bits).
%U http://arxiv.org/abs/0802.1237v2