| 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.