Notes - ADS HT24, Circulations

• Capacity constraints:
  • For each edge $e \in E$, $0 \le f(e) \le c(e)$
• Flow conservation:
  • $\sum _ {e \text{ into }v} f(e) - \sum _ {e \text{ out of }v}f(e) = d(v)$

Construct $(G’, s, t, c’)$ where:

• we add a source node $s$ and sink node $t$
• For each $v$ with $d(v) < 0$, add edge $(s, v)$ with capacity $ \vert d(v) \vert $.
• For each $v$ with $d(v) > 0$, add edge $(v, t)$ with capacity $d(v)$
• (and if $d(v) = 0$, then don’t add anything)

Then $G$ has a circulation iff $G’$ has a max flow equal to

\[D = \sum_{v \text{ s.t } d(v) > 0} d(v) = \sum_{v \text{ s.t. } d(v) < 0} |d(v)|\]

• Capacity constraints:
  • For each edge $e \in E$, $\ell (e) \le f(e) \le c(e)$
• Flow conservation:
  • $\sum _ {e \text{ into }v} f(e) - \sum _ {e \text{ out of }v}f(e) = d(v)$

Construct $(G’, c’, d’)$ as follows:

• Initialise $G’ = G$,$c’ = c, d’ = d$
• For each $e = (u, v)$ in $G$ with $\ell(e) > 0$
  • $d’(u) \leftarrow d’(u) + \ell(e)$
  • $d’(v) \leftarrow d’(v) - \ell(e)$
  • $c’(e) = c(e) - \ell(e)$

We can solve this using circulations with demands:

• Nodes for each consumer $i$ and product $j$
• Sink and source node
• Add edge $(i, j)$ with $[\ell, c] = [0, 1]$ (linking customers and products)
• Add edge $(s, i)$ with $[\ell, c] = [t _ i, t _ i’]$ (making sure we ask the right number of questions to each constumer)
• Add edge $(j, t)$ with $[\ell, c] = [p _ j, p _ j’]$ (making sure we get between $p _ j$ and $p _ j’$ responses for each product)
• Add edge $(t, s)$ with $[\ell, c] = [0, \infty]$ (any excess flow is okay)
• All demands are set to $0$

Then an integral circulation exists if and only if there is a feasible survey design, and for each edge $e = (i, j)$, we ask customer $i$ about product $j$ iff $f(e) = 1$.

This can be solved with a circulation network.

• For each flight $i$, add edge $(u _ i, v _ i)$ with $[\ell, c] = [1, 1]$ (this flight has to be covered)
• Add edge $(v _ i, u _ j)$ if flight $j$ is reachable from $i$ with $[\ell, c] = [0, 1]$ (we have the option to either use the same plane to cover flight $i$ and $j$, or not)
• Add source $s$ with demand $-k$
• Add sink $t$ with demand $k$
• Add edges $(s, u _ i)$, $(v _ i, t)$ with $[\ell, c] = [0, 1]$ (either use one of the $k$ planes at the start to cover flight $i$, or hope that it can be covered by another plane)

Then the flights can be performed iff there exists an integral circulation on this network.

• Suppose the flights can be performed with $k$ planes, then each plane defines a path $P$ from $s$ to $t$, send one unit of flow along edges of each path
• Suppose we have an integral circulation, consider an edge $(s, u _ i)$ that carries one unit of flow in $f$. By conservation $(u _ i, v _ i)$ carries one unit of flow. There is a unique edge out of $v _ i$ that carries one unit of flow. Continue until you reach $t$, get schedule for one of the $k$ planes.

This can be solved using circulation with demands.

Let $r _ i$ be the sum of row $i$ and let $c _ j$ be the sum of column $j$, and let $a _ {ij}$ be the element in the $(i, j)$-th entry of $A$. Let $R = \{u _ 1, \cdots, u _ m\}$, $C = \{v _ 1, \cdots, v _ n\}$ be disjoint sets of vertices.

For $i \in \{1, \cdots, m\}$ and $j \in \{1, \cdots, n\}$, add a directed edge $(u _ i, v _ j)$ and sets its capacity to $\lceil a _ {ij} \rceil$ and its lower bound to $\lfloor a _ {ij} \rfloor$.

Set the demand of $u _ i$ equal to $-r _ i$ and the demand of $v _ j$ to $c _ j$. We know that this circulation problem admits a feasible solution since for each $i, j$ we can set the flow on the edge $(u _ i, u _ j)$ equal to $a _ {ij}$. Therefore by running the Ford-Fulkerson algorithm, we can obtain an integer-valued circulation; the flow on each each gives the desired rounding of the matrix $A$.