Article ID: | iaor20102900 |
Volume: | 36 |
Issue: | 6 |
Start Page Number: | 680 |
End Page Number: | 683 |
Publication Date: | Nov 2008 |
Journal: | Operations Research Letters |
Authors: | Cardinal Jean, Fiorini Samuel, Joret Gwenal |
We study graph orientations that minimize the entropy of the in-degree sequence. 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.