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

Q. Q. Nong; Edwin Tai Chiu Cheng; Chi To Ng

doi:10.1016/j.tcs.2010.04.035

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

Q. Q. Nong, Edwin Tai Chiu Cheng, Chi To Ng

Research output: Journal article publication › Journal article › Academic research › peer-review

4 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 language	English
Pages (from-to)	2978-2986
Number of pages	9
Journal	Theoretical Computer Science
Volume	411
Issue number	31-33
DOIs	https://doi.org/10.1016/j.tcs.2010.04.035
Publication status	Published - 28 Jun 2010

Keywords

Polynomial-time algorithm
Ring loading problem
Weighted load

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

More information

10.1016/j.tcs.2010.04.035

Cite this

@article{8cd1968e02004bf99bfc237011042622,

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

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.",

keywords = "Polynomial-time algorithm, Ring loading problem, Weighted load",

author = "Nong, {Q. Q.} and Cheng, {Edwin Tai Chiu} and Ng, {Chi To}",

year = "2010",

month = jun,

day = "28",

doi = "10.1016/j.tcs.2010.04.035",

language = "English",

volume = "411",

pages = "2978--2986",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "31-33",

}

TY - JOUR

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

AU - Nong, Q. Q.

AU - Cheng, Edwin Tai Chiu

AU - Ng, Chi To

PY - 2010/6/28

Y1 - 2010/6/28

N2 - 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.

AB - 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.

KW - Polynomial-time algorithm

KW - Ring loading problem

KW - Weighted load

UR - http://www.scopus.com/inward/record.url?scp=77955429087&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2010.04.035

DO - 10.1016/j.tcs.2010.04.035

M3 - Journal article

SN - 0304-3975

VL - 411

SP - 2978

EP - 2986

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - 31-33

ER -

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

Abstract

Keywords

ASJC Scopus subject areas

More information

Other files and links

Fingerprint

Cite this