环上的最大流通量问题

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

Maximize the throughput of ring routing problem in SONET

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.