# A \(3/2\)-Approximation Algorithm for the Graph Balancing Problem with Two Weights
## 2 Algorithm
### Step 5.2  
Next, we cover the case when \(1/(k+1)<r\leq 1/k\) and \((k-1)/k\leq s<k/(k+1)\). In this case, it is possible that \(r+s\leq 1\). If \(OPT\leq 1\), at most one big edge can be oriented along with one small edge toward the same vertex; we exploit this property below. **Lemma 3**. : _For any \(k\geq 2\), there is a polynomial-time algorithm for the graph balancing problem with two rational weights \(r,s\), where \(1/(k+1)<r\leq 1/k\) and \((k-1)/k\leq s<k/(k+1)\) that either finds a solution of value at most \(3/2\) or proves that \(OPT>1\)._  
Proof. : We consider two cases: \(r+s>1\), and \(r+s\leq 1\). Assuming \(OPT\leq 1\), if \(r+s>1\) either at most one big edge is oriented towards a vertex or at most \(k\) small edges are oriented towards a vertex; apply Lemma 2 to obtain an orientation where each vertex has load at most \(3/2\), if such an orientation exists. From this point forward, assume \(r+s\leq 1\). Observe that \(2r+s>1\). If \(OPT\leq 1\), an optimal orientation either has at most a big edge oriented along with a small edge towards the same vertex, or at most \(k\) small edges are oriented towards a vertex. Like Lemma 2, compute a value \(\beta_{v}\) for the dedicated load of each \(v\in V\). When \(q_{v}\geq r+s\), set \(\beta_{v}=k\). Otherwise, if \(q_{v}\geq s\) set \(\beta_{v}=k-1\), and if not, assign \(\beta_{v}=p_{v}\) where \(q_{v}=p_{v}r\). The algorithm will build a modified version of the flow network \(N\) of Lemma 2, which we describe now. First, change the capacities on the arcs incident on the big edge nodes from \(k\) to \(k-1\). Second, for each \(v\in V\), set the capacity of the arc from buffer node \(v\) to vertex node \(v\) to \(k-1\) instead of \(k\). Leave the capacities from the vertex nodes to the sink \(\alpha_{2}\) as \(k-\beta_{v}\). We show this flow network in Figure 2. It is straightforward to see that this modified network maintains the same property that all the arcs leaving \(\alpha_{1}\) are saturated in an integral maximum flow if \(OPT\leq 1\). We modify the algorithm from Lemma 2 as follows. We refer the reader to BigSmall_rs (Algorithm 3). The modified flow network we described above is built for Step 1. Steps 2-3 are the same as before. In Step 4, when constructing the bipartite graph \(G^{\prime}\) between the big edge nodes and buffer nodes, \(V_{big}\) remains the same, but \(V_{rec}\) contains buffer nodes that receive instead at least \(\lceil(k-1)/2\rceil\) units of flow from a big edge node and  
\[E^{\prime}=\{(u,v)\mid u\in V_{big},v\in V_{rec},f(u,v)\geq\lceil(k-1)/2\rceil\}\]  
steps 5-8 remain the same as before. Since the capacities of the arcs leaving the buffer nodes and the incoming flow to the big edge nodes are one less than in the network in Lemma 2, one can show a matching on \(G^{\prime}\) exists if \(OPT\leq 1\) by replacing \(k\) with \(k-1\) and switching the even and odd cases of our original argument in Lemma 2. Consider the load of a vertex \(v\) in the orientation produced by the algorithm. Clearly any vertex \(v\) with \(q_{v}\geq r+s\) has \(\beta_{v}=k\) and \(k-\beta_{v}=0\). No flow is sent to these vertex nodes, so the load of these vertices is at most \(1\). Now, examine vertices with \(0\leq q_{v}<r+s\). If \(q_{v}\geq s\), then at most one additional small edge can be oriented towards \(v\). Hence, the load of \(v\) when \(q_{v}\geq s\) is at most \(q_{v}+r\leq 1+r\leq 3/2\) since \(r\leq 1/2\). Finally, consider when \(\beta_{v}=p_{v}\) and \(q_{v}=p_{v}r<s\). * Let \(v\) be a vertex with a big edge oriented towards it. At least \(\lceil(k-1)/2\rceil\) units of flow are sent from its big edge node to \(v\). Then, at most \((k-p_{v})-\lceil(k-1)/2\rceil\) small edges can be oriented along with the big edge towards \(v\). * Let \(v\) not have a big edge oriented towards it. At most \(k-p_{v}\) small edges are oriented towards \(v\).