Balancing congestion for unsplittable routing on a bidirected ring

Autor:	Becker, Johanna, Csizmadia, Zsolt, Laugier, Alexandre, Szabó, Jácint, Szegö, László
Rok vydání:	2010
Předmět:	Computer Science - Networking and Internet Architecture 90B10 90C10 94C15
Druh dokumentu:	Working Paper
Popis:	Given a bidirected ring with capacities and a demand graph, we present an approximation algorithm to the problem of finding the minimum $\alpha$ such that there exists a feasible unsplittable routing of the demands after multiplying each capacity by $\alpha$. We also give an approximation scheme to the problem.
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1006.0193 Zobrazit plný text záznamu View this record from Arxiv