TY - GEN

T1 - Approximation algorithms for the graph orientation minimizing the maximum weighted outdegree

AU - Asahiro, Yuichi

AU - Jansson, Jesper Andreas

AU - Miyano, Eiji

AU - Ono, Hirotaka

AU - Zenmyo, Kouhei

PY - 2007/12/1

Y1 - 2007/12/1

N2 - Given an undirected graph G = (V, E) and a weight function w : E → ℤ+, we consider the problem of orienting all edges in E so that the maximum weighted outdegree among all vertices is minimized. In this paper (1) we prove that the problem is strongly NP-hard if all edge weights belong to the set {1 ,k}, where k is any integer greater than or equal to 2, and that there exists no pseudo-polynomial time approximation algorithm for this problem whose approximation ratio is smaller than (1 + 1/k) unless P=NP; (2) we present a polynomial time algorithm that approximates the general version of the problem within a factor of (2 - 1/k), where k is the maximum weight of an edge in G; (3) we show how to approximate the special case in which all edge weights belong to {1, k} within a factor of 3/2 for k = 2 (note that this matches the inapproximability bound above), and (2 - 2/(k + 1)) for any k ≥ 3, respectively, in polynomial time.

AB - Given an undirected graph G = (V, E) and a weight function w : E → ℤ+, we consider the problem of orienting all edges in E so that the maximum weighted outdegree among all vertices is minimized. In this paper (1) we prove that the problem is strongly NP-hard if all edge weights belong to the set {1 ,k}, where k is any integer greater than or equal to 2, and that there exists no pseudo-polynomial time approximation algorithm for this problem whose approximation ratio is smaller than (1 + 1/k) unless P=NP; (2) we present a polynomial time algorithm that approximates the general version of the problem within a factor of (2 - 1/k), where k is the maximum weight of an edge in G; (3) we show how to approximate the special case in which all edge weights belong to {1, k} within a factor of 3/2 for k = 2 (note that this matches the inapproximability bound above), and (2 - 2/(k + 1)) for any k ≥ 3, respectively, in polynomial time.

UR - http://www.scopus.com/inward/record.url?scp=38149071598&partnerID=8YFLogxK

M3 - Conference article published in proceeding or book

SN - 9783540728689

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 167

EP - 177

BT - Algorithmic Aspects in Information and Management - Third International Conference, AAIM 2007, Proceedings

T2 - 3rd International Conference on Algorithmic Aspects in Information and Management, AAIM 2007

Y2 - 6 June 2007 through 8 June 2007

ER -