Oblivious Routing and Minimum Bisection

Abstract

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.

Publication
Seminar on Approximation Algorithms
Date