Minimum Entropy Orientations
| dc.creator | Cardinal, Jean | |
| dc.creator | Fiorini, Samuel | |
| dc.creator | Joret, Gwenaël | |
| dc.date | 2008-02-09 | |
| dc.date | 2008-09-22 | |
| dc.date.accessioned | 2026-07-07T10:13:08Z | |
| dc.date.available | 2026-07-07T10:13:08Z | |
| dc.description | 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). | |
| dc.description | Referees' comments incorporated | |
| dc.identifier | https://arxiv.org/abs/0802.1237 | |
| dc.identifier | http://arxiv.org/abs/0802.1237 | |
| dc.identifier | Operations Research Letters 36 (2008), pp. 680-683 | |
| dc.identifier | doi:10.1016/j.orl.2008.06.010 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/172425 | |
| dc.subject | Data Structures and Algorithms | |
| dc.subject | Discrete Mathematics | |
| dc.title | Minimum Entropy Orientations | |
| dc.type | text |