<p>In [1], Raghavan and Thompson showed that we can use randomized rounding to approximate integral multi-commodity flow and routing with congestion. The result is that suppose the optimal solution is <span class="math-container">$W$</span>, we can obtain, a solution <span class="math-container">$\le W+\sqrt{W\cdot O(\log n)}$</span> if <span class="math-container">$W\ge \Omega(\log n)$</span> with high probability.</p>
<p>However, in subsequent literature, e.g., [2], it is said that [1] achieves an approximation ratio of <span class="math-container">$O(\log n/ \log\log n)$</span>. How to transform the original result to this <span class="math-container">$O(\log n/ \log\log n)$</span> bound?</p>
<p>The proof in [1] basically uses the Chernoff bound, <span class="math-container">$\mathbb{P}[X\ge (1+\delta)W]\le \exp(-\delta^2 W/3)$</span>, by setting <span class="math-container">$\delta=\sqrt{O(\log n)/W}$</span>. I try to set <span class="math-container">$\delta=O(\log n/\log \log n)$</span> but this seems to not work.</p>
<p>[1] Raghavan and Thompson. <a href="https://dl.acm.org/doi/10.1007/BF02579324" rel="nofollow noreferrer">Randomized rounding: A technique for provably good algorithms and algorithmic proofs</a>.<br />
[2] Chuzhoy et al. <a href="https://www.cis.upenn.edu/%7Esanjeev/papers/stoc07_diredpwc.pdf" rel="nofollow noreferrer">Hardness of Routing with Congestion in Directed Graphs</a>.</p>

CC BY-SA 4.0
2023-11-22T20:00:46.020Z
This is standard material. It may help you to see the O(log n/log log n) approximation for congestion minimization. See book of Raghavan-Thomson or Chapter 5 in Williamson-Shmoys book or Chapter 7 of my notes https://courses.engr.illinois.edu/cs583/fa2021/approx-algorithms-lecture-notes.pdf. You can then adapt it for the maximization problem.
Chandra Chekuri
CC BY-SA 4.0
2023-11-23T04:53:56.530Z
@Chandra Chekuri Got it. Thanks for your help!
Recursion
CC BY-SA 4.0
2023-11-23T12:23:00.273Z
I meant book of Motwani-Raghavan on randomized algorithms, not book of Raghavan-Thompson.
Chandra Chekuri
<approximation-algorithms><randomized-algorithms><chernoff-bound><multicommodity-flow>
Approximation ratio of randomized rounding for integral multi-commodity flow
Recursion
# Approximation ratio of randomized rounding for integral multi-commodity flow

(Asked by: username_0 on 2023-11-22)

In [1], Raghavan and Thompson showed that we can use randomized rounding to approximate integral multi-commodity flow and routing with congestion. The result is that suppose the optimal solution is $W$, we can obtain, a solution $\le W+\sqrt{W\cdot O(\log n)}$ if $W\ge \Omega(\log n)$ with high probability.

However, in subsequent literature, e.g., [2], it is said that [1] achieves an approximation ratio of $O(\log n/ \log\log n)$. How to transform the original result to this $O(\log n/ \log\log n)$ bound?

The proof in [1] basically uses the Chernoff bound, $\mathbb{P}[X\ge (1+\delta)W]\le \exp(-\delta^2 W/3)$, by setting $\delta=\sqrt{O(\log n)/W}$. I try to set $\delta=O(\log n/\log \log n)$ but this seems to not work.

[1] Raghavan and Thompson. [Randomized rounding: A technique for provably good algorithms and algorithmic proofs](https://dl.acm.org/doi/10.1007/BF02579324).  
[2] Chuzhoy et al. [Hardness of Routing with Congestion in Directed Graphs](https://www.cis.upenn.edu/%7Esanjeev/papers/stoc07_diredpwc.pdf).

**Tags:** approximation-algorithms, randomized-algorithms, chernoff-bound, multicommodity-flow
> **Comments:**
> **username_1**: This is standard material. It may help you to see the O(log n/log log n) approximation for congestion minimization. See book of Raghavan-Thomson or Chapter 5 in Williamson-Shmoys book or Chapter 7 of my notes https://courses.engr.illinois.edu/cs583/fa2021/approx-algorithms-lecture-notes.pdf. You can then adapt it for the maximization problem.  
> **username_0**: @Chandra Chekuri Got it. Thanks for your help!  
> **username_1**: I meant book of Motwani-Raghavan on randomized algorithms, not book of Raghavan-Thompson.  

---

## 0 answers

