In the real world, it is usually cheaper when you buy some thing in a bulk because of the delivery costs. Now think about a undirected graph $G$ $=$ $(V,E)$ with length $l_e$ $\ge$ $0$ for all $e$ $\in$ $E$. This problem requires $k$ pairs of vertices $(s_i,t_i)$ and demand $d_i$. One thing that makes this problem interesting is that there is a cost function $f(u)$ such that satisfies following.
- $f(0)$ $=$ $0$
- $f$ is non-decreasing.
- $f$ is subadditive which means $f(x + y)$ $\le$ $f(x)$ $+$ $f(y)$ for all $x, y$ $\in$ $\mathbb{N}$
Now problem asks to find $k$ paths from $s_i$ to $t_i$ with capacity $c:E \rightarrow \mathbb{N}$ to minimize $\sum\limits_{e \in E}f(c_e)l_e$ such that for any edge we can send $d_i$ units of commodity from $s_i$ to $t_i$ at the same time without violating $c$.
Notice that this algorithm can be solved in polynomial time if $G$ is a tree. The reason is like follow. If you think about any possible path on a tree, there is a unique path from $u$ to $v$ where $u,v$ $\in$ $V$. Therefore, solution is just find a unique path and set the capacity and that’s all. Notice that this means it’s not just in polynomial time but it gives a trivial unique solution.
Now, let’s consider the following algorithm.
Find a tree metric $(V',T)$ that approximates $d$
$\operatorname{for}$ each pair of vertices $u,v$ in $V$
$\operatorname{for}$ each pair $s_i, t_i$
First of all, we need to show that there is a tree metric. Therefore we need to show that $d$ is a pseudometric. Notice that most of properties are trivial but only triangular inequality need to be more detial. Now, let’s think about any path between $(x,y)$ and $(y,z)$. Then, $d_{xy}$ $+$ $d_{yz}$ $=$ $\sum\limits_{e \in P_{xy}}l_e$ $+$ $\sum\limits_{e \in P_{yz}}l_e$ $=$ $\sum\limits_{e \in P_{xy} \cup P_{yz}}l_e$ $\ge$ $\sum\limits_{e \in P_{xz}}l_e$ $=$ $d_{xz}$. Notice that concatinating path from $x$ to $y$ and path from $y$ to $z$ is a path from $x$ to $z$. Which means at least longer or equal than “shortest” path from $x$ to $z$ in other world $P_{xy} \cup P_{yz}$ $\supseteq$ $P_{xz}$.
Now, problem is that we need to go through some $x$ that was not in $V$ but is in $V’$. Therefore, we need to remove every such vertices.
Here is another algorithm that gives a tree metric from a tree metric.
$\operatorname{while}$ $\exists v \in V$ and $v$'s parent $w$ such that $w$ was not a left node of $T$
return $(V, T')$
If given a tree metric $T$ can be like follow.
Then, other tree metric $T’$ can be like follow.
Then, this algorithm returns a tree metric on $V$ such that $T_{uv}$ $\le$ $T’_{uv}$ $\le$ $4T_{uv}$ for all $u,v$ $\in$ $V$. Notice that $T$ above is a result of original tree metric approximation algorithm. Proof is like follow.
First, $T’_{uv}$ $\le$ $T_{uv}$ untill we multiply 4 because we only merge the vertices. Therefore, $T’_{uv}$ $\le$ $4T_{uv}$ is true at the end of the algorithm.
Now, let’s recap some facts from the tree metric $T$.
- $\mathcal{L}_n$ is the level of the $n$. Notice that level of root node is $\log_2 \Delta$ and level of leaf node is $0$.
- $\mathcal{A}_{uv}$ is the least common ancestor of $u$ and $v$.
Then, $T_{uv}$ $=$ $2\sum_{k=1}^{\mathcal{L}_{\mathcal{A}_{uv}}}2^k$ $=$ $2^{\mathcal{L}_{\mathcal{A}_{uv}} + 2} - 4$ is true.
Now, let’s think about the smallest possible length for $T’_{uv}$. Then, $u$ and $v$ will go only to the parent and the possible most go is right below $\mathcal{A}_{uv}$. One of $u$ and $v$ may be can be merged to $\mathcal{A}_{uv}$ but not other one of $u$ and $v$ can be $\mathcal{A}_{uv}$. As a result, one of edge from $\mathcal{A}_{uv}$ to child will still left to exist. Therefore, $T’_{uv}$ $\ge$ $4 \cdot 2^{\mathcal{L}_{\mathcal{A}_{uv}}}$ $=$ $2^{\mathcal{L}_{\mathcal{A}_{uv}} + 2}$ $\ge$ $2^{\mathcal{L}_{\mathcal{A}_{uv}} + 2} - 4$ $=$ $T_{uv}$ Therefore, claim holds.
Notice that this means $d_{uv}$ $\le$ $T_{uv}$ $\le$ $T’_{uv}$ and $E[T’_{uv}]$ $\le$ $E[4T_{uv}]$ $=$ $4E[T_{uv}]$ $\le$ $O(\ln \left\vert V \right\vert)d_{uv}$. Therefore, $d_{uv}$ $\le$ $T’_{uv}$ and $E[T’_{uv}]$ $\le$ $O(\ln \left\vert V \right\vert)d_{uv}$.
Now, think about the algorithm follow.
Find a tree metric $(V',T)$ that approximates $d$
$(V,T')$ $\leftarrow$ $\operatorname{fit}(V, V', T)$
$\operatorname{for}$ each pair of vertices $u,v$ in $V$
$\operatorname{for}$ each pair $s_i, t_i$
Then this algorithm is a $O(\log n)$-approximation algorithm. Proof is like follow.
Let’s denote some terminologies.
- $P^{\star}_{u v}$ is the shortest path between $u$ and $v$ from the optimal solution.
- $c^{\star}_e$ for $e$ $\in$ $E$ is the capacity of $e$ from the optimal solution.
- $\operatorname{OPT}$ is the optimal solution; $\operatorname{OPT}$ $=$ $\sum\limits_{e \in E}f(\sum\limits_{i = 1 : e \in P^{\star}_{s_i t_i}}^{k} d_i)l_e$ $=$ $\sum\limits_{(u,v) \in E} f(\sum\limits_{i = 1 : (u,v) \in P^{\star}_{s_i t_i}}^{k} d_i)d_{uv}$ $=$ $\sum\limits_{(u,v) \in E} f(\sum\limits_{i = 1}^{k} d_i \mathbb{1}((u,v) \in P^{\star}_{s_i t_i})) d_{uv}$.
- $P’_{u v}$ is the unique shortest path between $u$ and $b$ from the $T’$.
- $P^{S}_{u v}$ is a path that changes each edge $(x,y)$ in $P^{\star}_{u v}$ to $P’_{x, y}$.
- $\operatorname{OPT’}$ is the solution from $P^{S}_{s_i t_i}$; $\operatorname{OPT’}$ $=$ $\sum\limits_{e \in T’}f(\sum\limits_{i = 1 : e \in P^{S}_{s_i t_i}}^{k} d_i)l_e$ $=$ $\sum\limits_{(x,y) \in T’} f(\sum\limits_{i = 1}^{k} d_i \sum\limits_{(u,v) \in E} \mathbb{1}((u,v) \in P^{\star}_{s_i t_i} \text{ and } (x,y) \in P’_{u v}))T’_{xy}$.
Notice that $P^{S}_{s_i t_i}$ may not be simple. Then, $E[\operatorname{OPT’}]$ $=$ $E[\sum\limits_{(x,y) \in T’} f(\sum\limits_{i = 1}^{k} d_i \sum\limits_{(u,v) \in E} \mathbb{1}((u,v) \in P^{\star}_{s_i t_i} \text{ and } (x,y) \in P’_{u v}))T’_{xy}]$ $\le$ $E[\sum\limits_{(x,y) \in T’} \sum\limits_{(u,v) \in E} f(\sum\limits_{i = 1}^{k}d_i \mathbb{1}((u,v) \in P^{\star}_{s_i t_i} \text{ and } (x,y) \in P’_{u v}))T’_{xy}]$ $=$ $E[\sum\limits_{(u,v) \in E} \sum\limits_{(x,y) \in T’} f(\sum\limits_{i = 1}^{k}d_i \mathbb{1}((u,v) \in P^{\star}_{s_i t_i} \text{ and } (x,y) \in P’_{u v}))T’_{xy}]$ $=$ $E[\sum\limits_{(u,v) \in E} \sum\limits_{(x,y) \in P’_{u v}} f(\sum\limits_{i = 1}^{k}d_i \mathbb{1}((u,v) \in P^{\star}_{s_i t_i}))T’_{xy}]$ $=$ $\sum\limits_{(u,v) \in E} E[ \sum\limits_{(x,y) \in P’_{u v}} f(\sum\limits_{i = 1}^{k}d_i \mathbb{1}((u,v) \in P^{\star}_{s_i t_i}))T’_{xy}]$ $=$ $\sum\limits_{(u,v) \in E} E[ f(\sum\limits_{i = 1}^{k}d_i \mathbb{1}((u,v) \in P^{\star}_{s_i t_i})) \sum\limits_{(x,y) \in P’_{u v}}T’_{xy}]$ $=$ $\sum\limits_{(u,v) \in E} f(\sum\limits_{i = 1}^{k} d_i \mathbb{1}((u,v) \in P^{\star}_{s_i t_i})) E[ \sum\limits_{(x,y) \in P’_{u v}}T’_{xy}]$ $=$ $\sum\limits_{(u,v) \in E} f(\sum\limits_{i = 1}^{k} d_i \mathbb{1}((u,v) \in P^{\star}_{s_i t_i})) E[T’_{uv}]$ $\le$ $\sum\limits_{(u,v) \in E} f(\sum\limits_{i = 1}^{k} d_i \mathbb{1}((u,v) \in P^{\star}_{s_i t_i})) O(\ln \left\vert V \right\vert)d_{uv}$ $=$ $O(\ln \left\vert V \right\vert) \sum\limits_{(u,v) \in E} f(\sum\limits_{i = 1}^{k} d_i \mathbb{1}((u,v) \in P^{\star}_{s_i t_i})) d_{uv}$ $=$ $O(\ln \left\vert V \right\vert) \operatorname{OPT}$.
Notice that following facts. First inequality holds because $f$ is subadditive. Third equality holds because $P’_{uv}$ $\in$ $T’$. Sixth equality holds because $f(\sum\limits_{i = 1}^{k} d_i \mathbb{1}((u,v) \in P^{\star}_{s_i t_i}))$ is independent from $u,v$. Seventh equality holds because $\sum\limits_{(x,y) \in P’_{u v}}T’_{xy}$ is the distance from $u$ to $v$. Therefore claim holds.
Simiallary, following is true.
Now let’s denote $\operatorname{ALG}$ as the value of the output solution. Then, $\operatorname{ALG}$ $=$ $\sum\limits_{(u,v) \in E} f(\sum\limits_{i = 1}^{k} d_i \sum\limits_{(x,y) \in T’} \mathbb{1}((x,y) \in P’_{s_i t_i} \text{ and } (u,v) \in P_{xy}))d_{uv}$ $\le$ $\sum\limits_{(u,v) \in E} \sum\limits_{(x,y) \in T’} f(\sum\limits_{i = 1}^{k} d_i \mathbb{1}((x,y) \in P’_{s_i t_i} \text{ and } (u,v) \in P_{xy}))d_{uv}$ $=$ $\sum\limits_{(x,y) \in T’} \sum\limits_{(u,v) \in E} f(\sum\limits_{i = 1}^{k} d_i \mathbb{1}((x,y) \in P’_{s_i t_i} \text{ and } (u,v) \in P_{xy}))d_{uv}$ $=$ $\sum\limits_{(x,y) \in T’} \sum\limits_{(u,v) \in P_{xy}} f(\sum\limits_{i = 1}^{k} d_i \mathbb{1}((x,y) \in P’_{s_i t_i}))d_{uv}$ $=$ $\sum\limits_{(x,y) \in T’} f(\sum\limits_{i = 1}^{k} d_i \mathbb{1}((x,y) \in P’_{s_i t_i})) \sum\limits_{(u,v) \in P_{xy}}d_{uv}$ $=$ $\sum\limits_{(x,y) \in T’} f(\sum\limits_{i = 1}^{k} d_i \mathbb{1}((x,y) \in P’_{s_i t_i})) d_{xy}$ $\le$ $\sum\limits_{(x,y) \in T’} f(\sum\limits_{i = 1}^{k} d_i \mathbb{1}((x,y) \in P’_{s_i t_i})) T’_{xy}$ $\le$ $\sum\limits_{(x,y) \in T’} f(\sum\limits_{i = 1}^{k} d_i \sum\limits_{(u,v) \in E} \mathbb{1}((u,v) \in P^{\star}_{s_i t_i} \text{ and } (x,y) \in P’_{u v}))T’_{xy}$ $=$ $\operatorname{OPT’}$.
All eqaulities and inequalities except last ineuqality can be proven in the same way with above. Therefore, we need to show only last inequality holds.
Proof for “$\sum\limits_{(x,y) \in T’} f(\sum\limits_{i = 1}^{k} d_i \mathbb{1}((x,y) \in P’_{s_i t_i})) T’_{xy}$ $\le$ $\sum\limits_{(x,y) \in T’} f(\sum\limits_{i = 1}^{k} d_i \sum\limits_{(u,v) \in E} \mathbb{1}((u,v) \in P^{\star}_{s_i t_i} \text{ and } (x,y) \in P’_{u v}))T’_{xy}$” is like follow.
Let’s think about “$\mathbb{1}((x,y) \in P’_{s_i t_i})$” and “$\sum\limits_{(u,v) \in E} \mathbb{1}((u,v) \in P^{\star}_{s_i t_i} \text{ and } (x,y) \in P’_{u v})$” for some $x, y, i$.
Then first one is $1$ if $(x,y) \in P’_{s_i t_i}$ and $0$ otherwise. Therefore, there is nothing to show if $(x,y) \not\in P’_{s_i t_i}$. Now, let’s assume that $(x,y) \in P’_{s_i t_i}$. Then, $P^{\star}_{s_i t_i}$ should include at least $(s_i,t_i)$ or longer path from $s_i$ to $t_i$ for any $i$. Which means the cardinarity of $\{(u,v) \in P^{\star}_{s_i t_i} \text{ and } (x,y) \in P’_{u v}\}$ should be bigger or equal than $1$. Therefore, claim holds. Notice that concatinating $(u,v) \in P^{\star}_{s_i t_i}$ in $T’$ will be a valid path from $u$ to $v$. Therefore, $(x,y)$ should be in some where in there.
As a result, $\operatorname{ALG}$ $\le$ $\operatorname{OPT’}$ $\le$ $O(\ln \left\vert V \right\vert) \operatorname{OPT}$. Therefore claim holds.
Notice that algorithm runs in a polynomial time.