Oblivious Routing and Minimum Bisection


Oblivious routing is generalization of multi commodity flows where the actual demand function is unknown. This paper proofs the existence of an approximate solution using tree metrics which can easily be transformed into an $\mathcal{O}(\log n)$ approximation algorithm. This result is then applied to the minimum bisection problem asking for an vertex bisection with minimal cost in the edges between the sets, also resulting in an $\mathcal{O}(\log n)$ approximation.

Seminar on Approximation Algorithms