A polynomial-time algorithm for the weighted link ring loading problem with integer demand splitting

Research output: Journal article publicationJournal articleAcademic researchpeer-review

2 Citations (Scopus)

Abstract

We are given an n-node undirected ring network, in which each link of the ring is associated with a weight. Traffic demand is given for each pair of nodes in the ring. Each demand is allowed to be split into two integer parts, which are then routed in different directions, clockwise and counterclockwise, respectively. The load of a link is the sum of the flows routed through the link and the nonnegative weighted load of a link is the product of its weight and its load. The objective is to find a routing scheme such that the maximum weighted load on the ring is minimized. Based on some useful structural properties of the decision version of the problem, we design a polynomial-time combinatorial algorithm for the optimization problem.
Original languageEnglish
Pages (from-to)2978-2986
Number of pages9
JournalTheoretical Computer Science
Volume411
Issue number31-33
DOIs
Publication statusPublished - 28 Jun 2010

Keywords

  • Polynomial-time algorithm
  • Ring loading problem
  • Weighted load

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this