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.

  • $\begingroup$ 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. $\endgroup$ Nov 22, 2023 at 20:00
  • $\begingroup$ @Chandra Chekuri Got it. Thanks for your help! $\endgroup$
    – Recursion
    Nov 23, 2023 at 4:53
  • $\begingroup$ I meant book of Motwani-Raghavan on randomized algorithms, not book of Raghavan-Thompson. $\endgroup$ Nov 23, 2023 at 12:23


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.