# A \(3/2\)-Approximation Algorithm for the Graph Balancing Problem with Two Weights
## 2 Algorithm
### Step 5.3  
For the final case in Step 5 of our algorithm, we apply a variant of the algorithm by [PERSON] _et al._[7]. First we give a brief explanation of their original algorithm that has approximation ratio \(7/4\). Let \(E^{B}\) be the set of big edges and let \(G^{B}=(V,E^{B})\) be the subgraph of \(G\) consisting of big edges. If \(OPT\leq 1\), every connected component of \(G^{B}\) with \(  
edge. In either case the maximum load of a vertex is at most \(7/4\). Note that a rotation does not change loads. Now we show how to modify this algorithm for our problem. **Lemma 4**. : _For every positive integer \(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 \(1/2<s<(k-1)/k\) that either finds a solution of value at most \(3/2\) or proves that \(OPT>1\)._  
Proof. : We make the following modifications to the algorithm in [7]. Consider any tree \(T\subseteq G^{B}\). Every big edge \(e\) has weight \(p_{e}=s\), so we simplify the tree constraint to  
\[\sum_{(v,e)\in L(T)}sx_{ev}\geq\left(\sum_{(v,e)\in L(T)}s\right)-s\Leftrightarrow \sum_{(v,e)\in L(T)}x_{ev}\geq|L(T)|-1\]  
Also, in the rounding procedure of [7] we change the leaf assignment and tree assignment:  
* _New leaf assignment_: if \(p_{e}x_{eu}\leq 1/2\), \(e\) is oriented towards \(v\). * _New tree assignment_: if \(p_{e}x_{eu}>1/2\), then \(e\) is a big edge and the connected component of \(G^{B}_{x}\) containing \(e\) is a tree \(T\). Orient all edges in \(T\) away from \(v\). Use the algorithm of [PERSON] _et al._[7] with the above modifications. If no fractional solution is found then no orientation exists; report FAIL if this is the case. Since modifying the above threshold from \(3/4\) to \(1/2\) will still allow all fractionally oriented edges to be rounded, the algorithm still finds an orientation in polynomial time. We can extend the arguments by [PERSON] _et al._[7] to show that the algorithm has approximation ratio \(3/2\) in our case. It is not hard to modify the proof of Theorem 1 in [7] to show that the following conditions are maintained by each vertex \(v\in V\) before and after each step in the rounding procedure. 1. The load of \(v\) is at most \(3/2\). 2. If \(e\in G_{x}\) is incident on \(v\), then \(v\) has load at most \(1+(s-1/2)\). 3. If \(e_{B}\) is a big edge in \(G^{B}_{x}\) incident on \(v\), the load of \(v\) is at most \(1\). 4. For any tree \(T\) that is a subgraph of \(G^{B}_{x}\), the tree constraint (Tree \(T\)) is never violated. For completeness we sketch a proof that the above conditions hold throughout the rounding procedure. At the beginning of the algorithm, after the modified LP1 is solved, all the conditions above are satisfied and the load of each vertex is at most \(1\). Next, we show conditions (1)-(4) are preserved for any vertex that changes its load during the rounding procedure. * _Tree assignment_: In a tree assignment, only vertices in the tree \(T\subseteq G^{B}_{x}\) containing big edge \(e=\{u,v\}\) for which \(p_{e}x_{eu}>1/2\) and \(v\) is a leaf of \(T\) have their loads modified. Every vertex in \(T\) is incident with a big edge in \(G_{x}\). Hence before this step is performed, by condition (3), each one of these vertices has load at most \(1\). Consider vertex \(u^{\prime}\) in \(T\) after the tree assignment has been performed. If \(u^{\prime}=v\), the load of \(v\) is decreased as big edges are oriented away from \(v\). If \(u^{\prime}\
eq v\), there exists a path \(P\) in \(T\) from \(u^{\prime}\) to \(v\). Say this path begins at edge \(e^{\prime}\). As \(P\) is a subtree of \(T\), it must satisfy our tightened tree constraint of LP1 and so \[x_{ev}+x_{e^{\prime}u^{\prime}}\geq|L(P)|-1=2-1=1\Leftrightarrow x_{e^{ \prime}u^{\prime}}\geq(1-x_{ev})=x_{eu}\] All the edges in \(P\) are big, so \(sx_{e^{\prime}u^{\prime}}\geq sx_{eu}>1/2\). Hence, the load of \(u^{\prime}\) increases by at most \(s-sx_{e^{\prime}u^{\prime}}<s-1/2\), and conditions (1) and (2) are satisfied for vertex \(u^{\prime}\).