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.
Type
Publication
Seminar on Approximation Algorithms
Markus Kaiser
Research Scientist
Research Associate at the University of Cambridge and Research Scientist at Siemens AG. I am interested in scalable Bayesian machine learning and Gaussian processes.