环上的最大流通量问题  

Maximize the throughput of ring routing problem in SONET

作　　者：陈智斌[1] 李建平[1] 

机构地区：[1]云南大学数学系,云南昆明650091

出　　处：《云南大学学报（自然科学版）》2004年第4期288-291,共4页Journal of Yunnan University(Natural Sciences Edition)

基　　金：国家自然科学基金资助项目(10271103);云南省自然科学基金资助项目(2003F0015M).

摘　　要：研究一个新颖的最大流通量问题,集中考察在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-近似多项式算法.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 e_i=(i,i+1) contains its integer capacity d_i and there exist m pairs of requests {s_i,t_i}(1≤i≤m and s_i≠t_i).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 s_i and t_i 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.

关 键 词：环 最大流通量 LP-rounding技巧 近似算法 NP-困难 

分 类 号：O153.3[理学—数学]