Balancing congestion for unsplittable routing on a bidirected ring

2010/06/01 by Johanna Becker, Zsolt Csizmadia, Becker, Johanna +7
Computer Science · Engineering · #90B10 #90C10 #94C15 #Advanced Optical Network Technologies #FOS: Computer and information sciences #Interconnection Networks and Systems #Network Traffic and Congestion Control #Networking and Internet Architecture (cs.NI)

paper · pdf · doi:10.48550/arxiv.1006.0193

openalex publication_date 2010/06/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Given a bidirected ring with capacities and a demand graph, we present an approximation algorithm to the problem of finding the minimum α such that there exists a feasible unsplittable routing of the demands after multiplying each capacity by α. We also give an approximation scheme to the problem.

Related

• A note on the ring loading problem
• An Improved Upper Bound for the Ring Loading Problem
• Approximation Algorithms for Minimizing Congestion in Demand-Aware Networks
• A Simple Approximation for a Hard Routing Problem
• On the Approximability of Robust Network Design