  Graph Balancing is the problem of orienting the edges of a weighted
multigraph so as to minimize the maximum weighted in-degree. Since the
introduction of the problem the best algorithm known achieves an approximation
ratio of $1.75$ and it is based on rounding a linear program with this exact
integrality gap. It is also known that there is no $(1.5 -
\epsilon)$-approximation algorithm, unless $\mathrm{P}=\mathrm{NP}$. Can we do
better than $1.75$? We prove that a different LP formulation, the configuration
LP, has a strictly smaller integrality gap. Graph Balancing was the last one in
a group of related problems from literature, for which it was open whether the
configuration LP is stronger than previous, simple LP relaxations. We base our
proof on a local search approach that has been applied successfully to the more
general Restricted Assignment problem, which in turn is a prominent special
case of makespan minimization on unrelated machines. With a number of technical
novelties we are able to obtain a bound of $1.749$ for the case of Graph
Balancing. It is not clear whether the local search algorithm we present
terminates in polynomial time, which means that the bound is non-constructive.
However, it is a strong evidence that a better approximation algorithm is
possible using the configuration LP and it allows the optimum to be estimated
within a factor better than $1.75$. A particularly interesting aspect of our
techniques is the way we handle small edges in the local search. We manage to
exploit the configuration constraints enforced on small edges in the LP. This
may be of interest to other problems such as Restricted Assignment as well.
