Balancing congestion for unsplittable routing on a bidirected ring

Johanna Becker, Zsolt Csizmadia, Alexandre Laugier, Jácint Szabó, László Szegö

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.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment