# A \(3/2\)-Approximation Algorithm for the Graph Balancing Problem with Two Weights
## 2 Algorithm
### Step 5.1
Similarly, for each edge \(\{u_{1},u_{2}\}\) represented by small edge node \(u\) and \(\gamma^{*}(u_{1},u_{2})=u_{i}\), send 1 unit of flow from \(\alpha_{1}\) to \(u\), from \(u\) to vertex node \(u_{i}\), and from \(u_{i}\) to \(\alpha_{2}\). It is not hard to see that this flow function is feasible and that no additional flow can be sent through the network. ```
Input: Multigraph \(G\). Note that \(k=\lfloor 1/r\rfloor\). Output: An orientation \(\gamma\) for the edges in \(E\) with maximum vertex load at most \(3/2\) or FAIL. If FAIL is returned there is no orientation for \(E\) with maximum vertex load 1. 1. Build the flow network \(N\). 2. Compute an integral maximum flow \(f\) of \(N\). 3. If all the arcs leaving the source are not saturated in \(f\), then return FAIL. 4. Construct bipartite graph \(G^{\prime}=(V_{big}\cup V_{rec},E^{\prime})\), where \(V_{big}\) is the set of big edge nodes, \(V_{rec}\) is the set of buffer nodes that receive at least \(\lceil k/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/2\rceil\}.\]
5. Compute a matching on \(G^{\prime}\) that matches each node in \(V_{big}\) with a unique vertex in \(V_{rec}\). 6. For each arc \((u,u_{i})\) in the matching of Step 5, orient big edge \(u\) towards vertex \(u_{i}\). 7. For each small edge node \(u\) and vertex node \(u_{i}\) with \(f(u,u_{i})=1\), orient \(u\) towards \(u_{i}\). 8. Return orientation for the edges of \(G\). ```  
**Algorithm 3**BigSmall_rs \((G=(V,E,\mathbf{p},\mathbf{q}))\)  
The time complexity of algorithm BigSmall_rs (Algorithm 3) is polynomial. Now we prove that this algorithm finds an orientation with maximal load at most \(3/2\) if \(OPT\leq 1\). If \(OPT\leq 1\), then as shown above, every small edge node receives 1 unit of flow from \(\alpha_{1}\). By flow conservation, each small edge node \(u\) sends its one unit of flow to a vertex node \(u_{i}\), and the algorithm orients small edge \(u\) towards vertex \(u_{i}\). As a result, every small edge is oriented by the algorithm. What remains to be shown is that all the big edges are oriented. The orientation of each big edge is determined by the matching computed by the algorithm. We must show this matching exists. Consider any subset \(V^{\prime}_{big}\subseteq V_{big}\), and denote the neighbourhood in \(G^{\prime}\) of this subset of nodes as \(N_{G^{\prime}}(V^{\prime}_{big})\). Note that \(N_{G^{\prime}}(V^{\prime}_{big})\subseteq V_{rec}\). To show the above matching exists, we prove \(|V^{\prime}_{big}|\leq|N_{G^{\prime}}(V^{\prime}_{big})|\). Two key observations are that the outdegree of every edge node is 2, and every big edge node is sent at most \(k\) units of flow. Furthermore, by flow conservation every big edge node must send at most \(k\) units of flow to the buffer nodes. We have two cases:  
* If \(k\) is odd, a buffer node in \(N_{G^{\prime}}(V^{\prime}_{big})\) can receive at least \(\lceil k/2\rceil\) units of flow from only one big edge node in \(V^{\prime}_{big}\) because \(k<2\cdot\lceil k/2\rceil\). Furthermore, since \(k-\lceil k/2\rceil=\lfloor k/2\rfloor<\lceil k/2\rceil\), each big edge node in \(G^{\prime}\) has degree 1. Hence, \(|V^{\prime}_{big}|=|N_{G^{\prime}}(V^{\prime}_{big})|\). * If \(k\) is even, \(\lceil k/2\rceil=k/2\), and a buffer node can receive \(k/2\) units of flow from at most two big edge nodes. Partition \(N_{G^{\prime}}(V^{\prime}_{big})\) into two disjoint sets \(N_{1}\) and \(N_{2}\), where \(N_{1}\) contains the buffer nodes that receive more than \(k/2\) units of flow from a big edge node, and \(N_{2}\) has the buffer nodes that receive \(k/2\) units of flow from a big edge node. Similar to when \(k\) is odd, each big edge node in \(V^{\prime}_{big}\) is adjacent to only one buffer node in \(N_{1}\), and so each buffer node in \(N_{1}\) has degree 1 in \(G^{\prime}\). This leaves \(|V^{\prime}_{big}|-|N_{1}|\) vertices adjacent to buffer nodes in \(N_{2}\).