# Notes - ADS HT24, Circulations

### Flashcards

Suppose:

- We have a circulation network $(G, c, d)$ where
- $G = (V, E)$
- $c : E \to \mathbb Z _ {> 0}$
- $d : V \to \mathbb Z$

What constraints do we have on a circulation $f : E \to \mathbb R _ {\ge 0}$?

- $G = (V, E)$
- $c : E \to \mathbb Z _ {> 0}$
- $d : V \to \mathbb Z$

- 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)$

Suppose we have a circulation network $(G, c, d)$ where

- $G = (V, E)$
- $c : E \to \mathbb Z _ {> 0}$
- $d : V \to \mathbb Z$

Describe the construction used to find a valid circulation $f$ by reducing it to a standard flow problem, and describe the condition which implies a valid circulation exists.

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)|\]Suppose:

- We have a circulation network $(G, c, d)$ where
- $G = (V, E)$
- $c : E \to \mathbb Z _ {> 0}$
- $\ell : E \to \mathbb Z _ {\ge 0}$
- $d : V \to \mathbb Z$

where in particular we now also lower bounds on the circulation. What constraints do we have on a circulation $f : E \to \mathbb R _ {\ge 0}$?

- $G = (V, E)$
- $c : E \to \mathbb Z _ {> 0}$
- $\ell : E \to \mathbb Z _ {\ge 0}$
- $d : V \to \mathbb Z$

- 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)$

Suppose:

- We have a circulation network $(G, c, d)$ where
- $G = (V, E)$
- $c : E \to \mathbb Z _ {> 0}$
- $\ell : E \to \mathbb Z _ {\ge 0}$
- $d : V \to \mathbb Z$

where in particular we now also lower bounds on the circulation. Describe the construction used to eliminate lower bounds and reduce it to an ordinary circulation problem.

- $G = (V, E)$
- $c : E \to \mathbb Z _ {> 0}$
- $\ell : E \to \mathbb Z _ {\ge 0}$
- $d : V \to \mathbb Z$

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)$

Suppose:

- We want to design a survery
- There are $n$ consumers and $m$ products
- We can only ask consumer $i$ about product $j$ if $i$ owns $j$
- We want to ask each consumer $i$ betwween $t _ i$ and $t _ i’$ questions
- We want between $p _ j$ and $p _ j’$ responses for product $j$

Can you describe the construction used to solve this problem?

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$.

Suppose:

- We want to know if we can use exactly $k$ planes to cover some flights
- $m$ flights, each described by:
- Origin city: $o _ i$
- Destination city: $d _ i$
- Departure time: $s _ i$
- Arrival time: $f _ i$

- We can use the same plane for flights $i$ and $j$ (“flight $i$ is reachable from flight “j”) if
- The destination of $i$ is the origin of $j$, i.e. $d _ i = o _ j$
- The arrival time of $f _ i$ is less than the departure time $o _ j$, i.e. $f _ i < o _ j$

Can you describe the construction used to solve this problem?

- Origin city: $o _ i$
- Destination city: $d _ i$
- Departure time: $s _ i$
- Arrival time: $f _ i$

- The destination of $i$ is the origin of $j$, i.e. $d _ i = o _ j$
- The arrival time of $f _ i$ is less than the departure time $o _ j$, i.e. $f _ i < o _ j$

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.

Suppose:

- $A$ is an $m \times n$ matrix whose entries are non-negative rational numbers
- The sum of the entries in each row and each column is an integer

Describe an efficient algorithm to round each entry $x$ of $A$ up or down so that each row sum and each column sum remains the same.

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$.