LNCS 2832 Efficient Algorithms for the Ring
Loading Problem with Demand Splitting 1st
edition by Biing Feng Wang, Yong Hsian Hsieh, Li
Pu Yeh ISBN 3540200649 978-3540200642 pdf
download
https://ebookball.com/product/lncs-2832-efficient-algorithms-for-
the-ring-loading-problem-with-demand-splitting-1st-edition-by-
biing-feng-wang-yong-hsian-hsieh-li-pu-yeh-
isbn-3540200649-978-3540200642-13034/
Explore and download more ebooks or textbooks
at ebookball.com
, Get Your Digital Files Instantly: PDF, ePub, MOBI and More
Quick Digital Downloads: PDF, ePub, MOBI and Other Formats
LNCS 2832 On Demand Broadcasting Under Deadline 1st edition by Bala
Kalyanasundaram, Mahe Velauthapillai ISBN 3540200649 978-3540200642
https://ebookball.com/product/lncs-2832-on-demand-broadcasting-
under-deadline-1st-edition-by-bala-kalyanasundaram-mahe-
velauthapillai-isbn-3540200649-978-3540200642-13344/
LNCS 2832 Approximating the Achromatic Number Problem on Bipartite
Graphs 1st edition by Guy Kortsarz, Sunil Shende ISBN 3540200649
978-3540200642
https://ebookball.com/product/lncs-2832-approximating-the-
achromatic-number-problem-on-bipartite-graphs-1st-edition-by-guy-
kortsarz-sunil-shende-isbn-3540200649-978-3540200642-9658/
LNCS 2832 Algorithms for Graph Rigidity and Scene Analysis 1st editon
by Alex Berg, Tibor Jordán ISBN 3540200649 978-3540200642
https://ebookball.com/product/lncs-2832-algorithms-for-graph-
rigidity-and-scene-analysis-1st-editon-by-alex-berg-tibor-jorda-
n-isbn-3540200649-978-3540200642-14056/
LNCS 2832 Lagrangian Relaxation for the k Median Problem: New Insights
and Continuity Properties 1st edition by Aaron Archer, Ranjithkumar
Rajagopalan, David Shmoys ISBN 3540200649 978-3540200642
https://ebookball.com/product/lncs-2832-lagrangian-relaxation-
for-the-k-median-problem-new-insights-and-continuity-
properties-1st-edition-by-aaron-archer-ranjithkumar-rajagopalan-
david-shmoys-isbn-3540200649-978-3540200642-14478/
,LNCS 2832 An Efficient Implementation of a Quasi polynomial Algorithm
for Generating Hypergraph Transversals 1st edition by Boros,
Elbassioni, Gurvich, Leonid Khachiyan ISBN 3540200649 978-3540200642
https://ebookball.com/product/lncs-2832-an-efficient-
implementation-of-a-quasi-polynomial-algorithm-for-generating-
hypergraph-transversals-1st-edition-by-boros-elbassioni-gurvich-
leonid-khachiyan-isbn-3540200649-978-3540200642-109/
LNCS 2832 Sublinear Computing Invited Lecture 1st edition by Bernard
Chazelle ISBN 3540200649 978-3540200642
https://ebookball.com/product/lncs-2832-sublinear-computing-
invited-lecture-1st-edition-by-bernard-chazelle-
isbn-3540200649-978-3540200642-13124/
LNCS 2832 Finding Short Integral Cycle Bases for Cyclic Timetabling
1st edition by Christian Liebchen ISBN 3540200649 978-3540200642
https://ebookball.com/product/lncs-2832-finding-short-integral-
cycle-bases-for-cyclic-timetabling-1st-edition-by-christian-
liebchen-isbn-3540200649-978-3540200642-11900/
LNCS 2832 Fast Integer Programming in Fixed Dimension 1st edition by
Friedrich Eisenbrand ISBN 3540200649 978-3540200642
https://ebookball.com/product/lncs-2832-fast-integer-programming-
in-fixed-dimension-1st-edition-by-friedrich-eisenbrand-
isbn-3540200649-978-3540200642-10218/
LNCS 2832 The Fractional Prize Collecting Steiner Tree Problem on
Trees 1st edition by Gunnar Klau, Ivana Ljubic, Petra Mutzel, Ulrich
Pferschy, René Weiskircher ISBN 3540200649 978-3540200642
https://ebookball.com/product/lncs-2832-the-fractional-prize-
collecting-steiner-tree-problem-on-trees-1st-edition-by-gunnar-
klau-ivana-ljubic-petra-mutzel-ulrich-pferschy-rena-c-
weiskircher-isbn-3540200649-978-3540200642-9672/
, Efficient Algorithms for the Ring Loading
Problem with Demand Splitting
Biing-Feng Wang, Yong-Hsian Hsieh, and Li-Pu Yeh
Department of Computer Science, National Tsing Hua University Hsinchu, Taiwan
30043, Republic of China,
, {eric,lee}@venus.cs.nthu.edu.tw
Fax: 886-3-5723694
Abstract. Given a ring of size n and a set K of traffic demands, the
ring loading problem with demand splitting (RLPW) is to determine a
routing to minimize the maximum load on the edges. In the problem,
a demand between two nodes can be split into two flows and then be
routed along the ring in different directions. If the two flows obtained
by splitting a demand are restricted to integers, this restricted version is
called the ring loading problem with integer demand splitting (RLPWI).
In this paper, efficient algorithms are proposed for the RLPW and the
RLPWI. Both the proposed algorithms require O(|K| + ts ) time, where
ts is the time for sorting |K| nodes. If |K| ≥ n for some small constant
> 0, integer sort can be applied and thus ts = O(|K|); otherwise,
ts = O(|K| log |K|). The proposed algorithms improve the previous
upper bounds from O(n|K|) for both problems.
Keywords: Optical networks, rings, routing, algorithms, disjoint-set
data structures
1 Introduction
Let R be a ring network of size n, in which the node-set is {1, 2, . . . , n} and
the edge-set is E ={(1, 2), (2, 3), . . . , (n − 1, n), (n, 1)}. Let K be a set of
traffic demands, each of which is described by an origin-destination pair of nodes
together with an integer specifying the amount of traffic requirement. The ring
is undirected. Each demand can be routed along the ring in any of the two
directions, clockwise and counterclockwise. A demand between two nodes i and
j, where i < j, is routed in the clockwise direction if it passes through the node
sequence (i, i + 1, . . . , j ), and is routed in the counterclockwise direction if it
passes through the node sequence (i, i − 1, . . . , 1, n, n − 1, . . . , j ). The load
of an edge is the total traffic flow passing through it. Given the ring-size n and
the demand-set K, the ring loading problem (RLP ) is to determine a routing to
minimize the maximum load of the edges.
There are two kinds of RLP. If each demand in K must be routed entirely in
either of the directions, the problem is called the ring loading problem without
demand splitting (RLPWO). Otherwise, the problem is called the ring loading
G. Di Battista and U. Zwick (Eds.): ESA 2003, LNCS 2832, pp. 517–526, 2003.
c Springer-Verlag Berlin Heidelberg 2003
Loading Problem with Demand Splitting 1st
edition by Biing Feng Wang, Yong Hsian Hsieh, Li
Pu Yeh ISBN 3540200649 978-3540200642 pdf
download
https://ebookball.com/product/lncs-2832-efficient-algorithms-for-
the-ring-loading-problem-with-demand-splitting-1st-edition-by-
biing-feng-wang-yong-hsian-hsieh-li-pu-yeh-
isbn-3540200649-978-3540200642-13034/
Explore and download more ebooks or textbooks
at ebookball.com
, Get Your Digital Files Instantly: PDF, ePub, MOBI and More
Quick Digital Downloads: PDF, ePub, MOBI and Other Formats
LNCS 2832 On Demand Broadcasting Under Deadline 1st edition by Bala
Kalyanasundaram, Mahe Velauthapillai ISBN 3540200649 978-3540200642
https://ebookball.com/product/lncs-2832-on-demand-broadcasting-
under-deadline-1st-edition-by-bala-kalyanasundaram-mahe-
velauthapillai-isbn-3540200649-978-3540200642-13344/
LNCS 2832 Approximating the Achromatic Number Problem on Bipartite
Graphs 1st edition by Guy Kortsarz, Sunil Shende ISBN 3540200649
978-3540200642
https://ebookball.com/product/lncs-2832-approximating-the-
achromatic-number-problem-on-bipartite-graphs-1st-edition-by-guy-
kortsarz-sunil-shende-isbn-3540200649-978-3540200642-9658/
LNCS 2832 Algorithms for Graph Rigidity and Scene Analysis 1st editon
by Alex Berg, Tibor Jordán ISBN 3540200649 978-3540200642
https://ebookball.com/product/lncs-2832-algorithms-for-graph-
rigidity-and-scene-analysis-1st-editon-by-alex-berg-tibor-jorda-
n-isbn-3540200649-978-3540200642-14056/
LNCS 2832 Lagrangian Relaxation for the k Median Problem: New Insights
and Continuity Properties 1st edition by Aaron Archer, Ranjithkumar
Rajagopalan, David Shmoys ISBN 3540200649 978-3540200642
https://ebookball.com/product/lncs-2832-lagrangian-relaxation-
for-the-k-median-problem-new-insights-and-continuity-
properties-1st-edition-by-aaron-archer-ranjithkumar-rajagopalan-
david-shmoys-isbn-3540200649-978-3540200642-14478/
,LNCS 2832 An Efficient Implementation of a Quasi polynomial Algorithm
for Generating Hypergraph Transversals 1st edition by Boros,
Elbassioni, Gurvich, Leonid Khachiyan ISBN 3540200649 978-3540200642
https://ebookball.com/product/lncs-2832-an-efficient-
implementation-of-a-quasi-polynomial-algorithm-for-generating-
hypergraph-transversals-1st-edition-by-boros-elbassioni-gurvich-
leonid-khachiyan-isbn-3540200649-978-3540200642-109/
LNCS 2832 Sublinear Computing Invited Lecture 1st edition by Bernard
Chazelle ISBN 3540200649 978-3540200642
https://ebookball.com/product/lncs-2832-sublinear-computing-
invited-lecture-1st-edition-by-bernard-chazelle-
isbn-3540200649-978-3540200642-13124/
LNCS 2832 Finding Short Integral Cycle Bases for Cyclic Timetabling
1st edition by Christian Liebchen ISBN 3540200649 978-3540200642
https://ebookball.com/product/lncs-2832-finding-short-integral-
cycle-bases-for-cyclic-timetabling-1st-edition-by-christian-
liebchen-isbn-3540200649-978-3540200642-11900/
LNCS 2832 Fast Integer Programming in Fixed Dimension 1st edition by
Friedrich Eisenbrand ISBN 3540200649 978-3540200642
https://ebookball.com/product/lncs-2832-fast-integer-programming-
in-fixed-dimension-1st-edition-by-friedrich-eisenbrand-
isbn-3540200649-978-3540200642-10218/
LNCS 2832 The Fractional Prize Collecting Steiner Tree Problem on
Trees 1st edition by Gunnar Klau, Ivana Ljubic, Petra Mutzel, Ulrich
Pferschy, René Weiskircher ISBN 3540200649 978-3540200642
https://ebookball.com/product/lncs-2832-the-fractional-prize-
collecting-steiner-tree-problem-on-trees-1st-edition-by-gunnar-
klau-ivana-ljubic-petra-mutzel-ulrich-pferschy-rena-c-
weiskircher-isbn-3540200649-978-3540200642-9672/
, Efficient Algorithms for the Ring Loading
Problem with Demand Splitting
Biing-Feng Wang, Yong-Hsian Hsieh, and Li-Pu Yeh
Department of Computer Science, National Tsing Hua University Hsinchu, Taiwan
30043, Republic of China,
, {eric,lee}@venus.cs.nthu.edu.tw
Fax: 886-3-5723694
Abstract. Given a ring of size n and a set K of traffic demands, the
ring loading problem with demand splitting (RLPW) is to determine a
routing to minimize the maximum load on the edges. In the problem,
a demand between two nodes can be split into two flows and then be
routed along the ring in different directions. If the two flows obtained
by splitting a demand are restricted to integers, this restricted version is
called the ring loading problem with integer demand splitting (RLPWI).
In this paper, efficient algorithms are proposed for the RLPW and the
RLPWI. Both the proposed algorithms require O(|K| + ts ) time, where
ts is the time for sorting |K| nodes. If |K| ≥ n for some small constant
> 0, integer sort can be applied and thus ts = O(|K|); otherwise,
ts = O(|K| log |K|). The proposed algorithms improve the previous
upper bounds from O(n|K|) for both problems.
Keywords: Optical networks, rings, routing, algorithms, disjoint-set
data structures
1 Introduction
Let R be a ring network of size n, in which the node-set is {1, 2, . . . , n} and
the edge-set is E ={(1, 2), (2, 3), . . . , (n − 1, n), (n, 1)}. Let K be a set of
traffic demands, each of which is described by an origin-destination pair of nodes
together with an integer specifying the amount of traffic requirement. The ring
is undirected. Each demand can be routed along the ring in any of the two
directions, clockwise and counterclockwise. A demand between two nodes i and
j, where i < j, is routed in the clockwise direction if it passes through the node
sequence (i, i + 1, . . . , j ), and is routed in the counterclockwise direction if it
passes through the node sequence (i, i − 1, . . . , 1, n, n − 1, . . . , j ). The load
of an edge is the total traffic flow passing through it. Given the ring-size n and
the demand-set K, the ring loading problem (RLP ) is to determine a routing to
minimize the maximum load of the edges.
There are two kinds of RLP. If each demand in K must be routed entirely in
either of the directions, the problem is called the ring loading problem without
demand splitting (RLPWO). Otherwise, the problem is called the ring loading
G. Di Battista and U. Zwick (Eds.): ESA 2003, LNCS 2832, pp. 517–526, 2003.
c Springer-Verlag Berlin Heidelberg 2003
