2008/02/29 by Jean Cardinal, Samuel Fiorini, Gwenaël Joret
Computer Science · #Algorithms and Data Compression #Cellular Automata and Applications #Computational Geometry and Mesh Generation #cs.DM #cs.DS
paper · pdf · doi:10.1016/j.orl.2008.06.010
published as Operations Research Letters 36 (2008), pp. 680-683 · Referees' comments incorporated
openalex publication_date 2008/07/23 · arxiv created 2008/09/22 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
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 log2 e bits (approx. 1.4427 bits).