# A \(3/2\)-Approximation Algorithm for the Graph Balancing Problem with Two Weights
## 2 Algorithm
### Step 5.1  
Next, we consider the case handled in Step 5.1 of the algorithm, namely when \(k/(k+1)\leq s\leq 1\) and \(k=\lfloor 1/r\rfloor\) so \(1/(k+1)<r\leq 1/k\). In Lemma 2, we utilize the property that \(r+s>1\), which means that if \(OPT\leq 1\), then no small edge can be oriented with a big edge towards a given vertex without causing the maximal load to be greater than \(1\). **Lemma 2**: _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/(k+1)\leq s\leq 1\) that either finds a solution of value at most \(3/2\) or proves that \(OPT>1\)._  
If \(OPT\leq 1\), since \(r+s>1\), for any optimal orientation either at most a big edge is oriented towards a vertex, or at most \(k\) small edges are oriented towards a vertex. This property is natural to encode into a flow network. To find an orientation for the edges of the weighted multigraph \(G=(V,E,\mathbf{p},\mathbf{q})\), we use a multi-level flow network similar to that in [9]. We build a flow network \(N\) as follows. First, we consider the dedicated loads of the vertices. For each vertex \(v\in V\), define a value \(\beta_{v}\geq 0\) as follows: if \(q_{v}\geq s\), set \(\beta_{v}=k\); otherwise there is a non-negative integer \(p_{v}\) so that \(q_{v}=p_{v}r\), assign \(\beta_{v}=p_{v}\). The flow network will have a source \(\alpha_{1}\) and sink \(\alpha_{2}\). We will describe the network level by level. First, we have a level of nodes in the network called _edge nodes_. These are nodes corresponding to the edges in the multigraph. There are two types of edge nodes: big edge nodes for edges with weight \(s\); and small edge nodes for those with weight \(r\). From source \(\alpha_{1}\), add an arc from \(\alpha_{1}\) to each edge node, and set its capacity to \(k\) if it is to a big edge node, and \(1\) otherwise. The next level consists of _buffer nodes_, one for each vertex. The buffer nodes are added to prevent excess flow from being contributed by the big edge nodes. While this part of the network is not important for proving this lemma, it will be vital for how we later use this network in Lemma 3. For each big edge \(\{u,v\}\in E\), add arcs with capacity \(k\) from its big edge node to buffer nodes \(u\) and \(v\). For the next level of the network, create a _vertex node_ that will correspond to each vertex in the multigraph. For each buffer node for \(v\in V\), add an arc from its buffer node to its vertex node with capacity \(k\). Next, for each small edge \(\{u,v\}\in E\), include arcs with capacity \(1\) from its small edge node to vertex nodes \(u\) and \(v\). Finally, for each vertex \(v\in V\), add an arc from vertex node \(v\) to sink \(\alpha_{2}\) with capacity \(k-\beta_{v}\). The resulting flow network is shown in Figure 1.  
Before we proceed to describe the algorithm, we show that this network has the following property: if \(OPT\leq 1\), an integral maximum flow on this network saturates all the arcs leaving source \(\alpha_{1}\). Consider any optimal orientation \(\gamma^{*}\). Using \(\gamma^{*}\) we construct a flow function in  
Figure 1: The flow network \(N\) for the case when \(1/(k+1)<r\leq 1/k\) and \(k/(k+1)\leq s\leq 1\). Shaded nodes represent big edge nodes, and each black node is a buffer node associated with one vertex node. Arcs that are unlabelled have flow capacity \(1\). which every small edge node receives 1 unit of flow, and each big edge node receives \(k\) units of flow from the source \(\alpha_{1}\). For each big edge \(\{u_{1},u_{2}\}\) of \(G\) with \(\gamma^{*}(u_{1},u_{2})=u_{i}\), if \(u\) is the big edge node for \(\{u_{1},u_{2}\}\) send \(k\) units of flow from \(\alpha_{1}\) to \(u\), \(k\) units of flow from \(u\) to buffer node \(u_{i}\), \(k\) units of flow from buffer node \(u_{i}\) to vertex node \(u_{i}\), and \(k\) units of flow from \(u_{i}\) to the sink \(\alpha_{2}\).