Minimum Entropy Orientations

Details Minimum Entropy Orientations Minimum Entropy Orientations

2008-02-09

arxiv.org/abs/0802.1237v2

Operations Research Letters 36 (2008), pp. 680-683

Computer Science

Data Structures and Algorithms

Referees' comments incorporated

Scientific paper

10.1016/j.orl.2008.06.010

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

Affiliated with

Also associated with

No associations

Rating

Minimum Entropy Orientations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Minimum Entropy Orientations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Minimum Entropy Orientations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-402670