Graph orientation algorithms to minimize the maximum outdegree
This paper studies the problem of orienting all edges of a weighted graph such that the maximum weighted outdegree of vertices is minimized. This problem, which has applications in the guard arrangement for example, can be shown to be NP-hard generally. In this paper we first give optimal orientation algorithms which run in polynomial time for the following special cases: (i) the input is an unweighted graph, and (ii) the input graph is a tree. Then, by using those algorithms as sub-procedures, we provide a simple, combinatorial, min {w(max)/w(min) (2 - epsilon)}-approximation algorithm for the general case, where W-max and w(min) are the maximum and the minimum weights of edges, respectively, and epsilon is some small positive real number that depends on the input.
graph orientation np-hardness min-max optimization approximation algorithms