@inproceedings{bece0a05f0fe4644b8420906ed224540,
title = "On the most imbalanced orientation of a graph",
abstract = "We study the problem of orienting the edges of a graph such that the minimum over all the vertices of the absolute difference between the outdegree and the indegree of a vertex is maximized. We call this minimum the imbalance of the orientation, i.e. the higher it gets, the more imbalanced the orientation is. We study this problem denoted by MaxIm. We first present different characterizations of the graphs for which the optimal objective value of MaxIm is zero. Next we show that it is generally NP-complete and cannot be approximated within a ratio of 1/2 + ε for any constant ε > 0 in polynomial time unless P = NP even if the minimum degree of the graph δ equals 2. Finally we describe a polynomial-time approximation algorithm whose ratio is equal to 1/2 for graphs where δ ≡ 0[4] or δ ≡ 1[4] and (1/2-1/δ) for general graphs.",
author = "Walid Ben-Ameur and Antoine Glorieux and Jos{\'e} Neto",
note = "Publisher Copyright: {\textcopyright} Springer International Publishing Switzerland 2015.; 21st International Conference on Computing and Combinatorics Conference, COCOON 2015 ; Conference date: 04-08-2015 Through 06-08-2015",
year = "2015",
month = jan,
day = "1",
doi = "10.1007/978-3-319-21398-9\_2",
language = "English",
isbn = "9783319213972",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "16--29",
editor = "Dachuan Xu and Donglei Du and Dingzhu Du",
booktitle = "Computing and Combinatorics - 21st International Conference, COCOON 2015, Proceedings",
}