# Approximation ratio of randomized rounding for integral multi-commodity flow

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.
[2] Chuzhoy et al. Hardness of Routing with Congestion in Directed Graphs.

• 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 courses.engr.illinois.edu/cs583/fa2021/…. You can then adapt it for the maximization problem. Commented Nov 22, 2023 at 20:00
• @Chandra Chekuri Got it. Thanks for your help! Commented Nov 23, 2023 at 4:53
• I meant book of Motwani-Raghavan on randomized algorithms, not book of Raghavan-Thompson. Commented Nov 23, 2023 at 12:23