# A \(3/2\)-Approximation Algorithm for the Graph Balancing Problem with Two Weights
## 1 Introduction  
Let \(G=(V,E,\mathbf{p},\mathbf{q})\) be a weighted multigraph, where \(V\) is the set of vertices, \(E\) is the set of edges, \(\mathbf{p}=(p_{1},\ldots,p_{|E|})\) are non-negative edge weights, and \(\mathbf{q}=(q_{1},\ldots,q_{|V|})\) are the dedicated loads. A _dedicated load_\(q_{v}\) of vertex \(v\) is the sum of the weights of self-loops incident on \(v\) in the multigraph; we assume the self-loops are removed from \(G\). An _orientation_\(\gamma:E\to V\) orients each edge \(e\in E\) towards one of its endpoints. Given a weighted multigraph \(G\), the _graph balancing problem_ is to find an orientation \(\gamma\) where the maximum load of the vertices is minimized, where the load of a vertex \(v\) is defined as \(q_{v}+\sum_{|\gamma(e)=v}p_{e}\). Let \(r,s\in\mathbb{Z}^{+}\), where \(r<s\). We focus on a special case of this problem we call the _graph balancing problem with two weights_ (GBP2W), where the edges have either weight \(r\) or \(s\) and each dedicated load is of the form \(ar+bs\) for \(a,b\in\mathbb{Z}^{+}\cup\{0\}\). The graph balancing problem is a special case of the makespan minimization problem on unrelated parallel machines (\(R||C_{max}\) in Graham notation, see [1]). Presently, the best-known approximation algorithms for \(R||C_{max}\) have approximation ratio \(2\). The first \(2\)-approximation algorithm for \(R||C_{max}\) was presented by [PERSON] _et al._[2], and in 2005 a \((2-1/m)\)-approximation algorithm was given by [PERSON] and [PERSON] [3], where \(m\) is the number of machines. These \(2\)-approximation algorithms utilize linear programming, but it is worth noting that there is a combinatorial \(2\)-approximation algorithm by [PERSON] _et al._[4] that employs generalized flow networks. Finding an approximation algorithm with approximation ratio better than \(2\) for \(R||C_{max}\) is an important open problem in scheduling theory, and trying to get any further insight into the problem through the study of subclasses of \(R||C_{max}\) has been of attention lately [5; 6; 7; 8; 9; 10; 11; 12; 13]. Recently, [PERSON] _et al._[7] gave a \(7/4\)-approximation algorithm for the graph balancing problem. In addition, [PERSON] _et al._[14] showed that for \(p<3/2\), there is no \(p\)-approximationalgorithm for the graph balancing problem when the edges of the multigraph have weight \(1/2\) or \(1\), unless P\(=\)NP. Note that this hardness result was also independently proven by [PERSON] _et al._[5; 15]. This matches the inapproximability bound for the makespan minimization problem on unrelated parallel machines given by [PERSON] _et al._[2], so, GBP2W is worth investigating due to being one of the simplest scheduling problems presently known to share inapproximability properties with \(R||C_{max}\). 3/2-approximation algorithms have been presented for some special cases of GBP2W. The _graph orientation problem with two weights_ is a NP-hard special case of GBP2W where \(G\) is simple, and every dedicated load \(q_{v}=0\). In [5; 15], [PERSON] _et al._ gave two approximation algorithms that achieve the bound 3/2 for variants of the graph orientation problem with two weights: one called _Cycle-Canceling_ when \(r=1\) and \(s=2\); and another called _Refined Cycle-Canceling_ when \(r=1\) and \(s=3\). Later, [PERSON] and [PERSON] [9] gave a 3/2-approximation algorithm for GBP2W when \(r=1\) and \(s=k\), where \(k\) is a positive integer (Theorem 4.1). Most recently, [PERSON] and [PERSON] [9] presented a 1.652-approximation algorithm for GBP2W. Their approximation algorithm employs binary search, and for a given estimation of the optimal load \(T\) different approximation algorithms are used based on the values of the weights with respect to \(T\). A core component of this approximation algorithm is a flow-network based approximation algorithm for the two-valued case of the restricted assignment problem introduced in the same paper. In this paper we present a 3/2-approximation algorithm for GBP2W.