陈智斌, 李建平. 环上的最大流通量问题[J]. 云南大学学报(自然科学版), 2004, 26(4): 288-291.
引用本文: 陈智斌, 李建平. 环上的最大流通量问题[J]. 云南大学学报(自然科学版), 2004, 26(4): 288-291.
CHEN Zhi-bin, LI Jian-ping. Maximize the throughput of ring routing problem in SONET[J]. Journal of Yunnan University: Natural Sciences Edition, 2004, 26(4): 288-291.
Citation: CHEN Zhi-bin, LI Jian-ping. Maximize the throughput of ring routing problem in SONET[J]. Journal of Yunnan University: Natural Sciences Edition, 2004, 26(4): 288-291.

环上的最大流通量问题

Maximize the throughput of ring routing problem in SONET

  • 摘要: 研究一个新颖的最大流通量问题,集中考察在SONET环上的情形,即令R为SONET上的一个环,其顶点集0,1,2,…,n-1,每条边ei=(i,i+1)和边上的整数容量限制di及m个所要求通过的点对si,ti(1≤i≤m且si≠ti).要求一个方案,选择所要求的m个点对中的某些点对(也许是所有的),此时每个点对就由一条道路相连,在通过环上每条边的总条数不超过其边整数容量限制的条件下,最大化所用到的道路条数.通过引入单方向概念并应用LP-rounding技巧,证明了环上的单方向最大流通量问题属于P类,即可有多项式时间算法求解,并因此获得了环上最大流通量问题的一个2-近似多项式算法.

     

    Abstract: A novel problem of maximizing throughput of requests was studied on the ring network in SONET,i.e.,let R be a ring on vertices 0,1,…,n-1 in SONET,each edge ei=(i,i+1) contains its integer capacity di and there exist m pairs of requests si,ti(1≤i≤m and si≠ti).The objective of this problem was to route some (maybe all) of these m requests so as to maximize the number of the different paths used,each connecting si and ti and satisfying the amount of paths through each edge is not beyond its integer capacity of that edge. By using the concept of one-direction and the technique of LP-rounding, the problem of ring with one direction was proved to be in P,i.e.,there exists a polynomially optimal algorithm that can solves it.Moreover,a 2-approximation algorithm to this problem in ring network was given thereby.

     

/

返回文章
返回