Optimal oblivious routing in polynomial time
Optimal oblivious routing in polynomial time
复制标题
DOI：
10.1145/780542.780599
复制
发表时间：
2003-06
期刊：
影响因子：
--
通讯作者：
Y. Azar;Edith Cohen;A. Fiat;Haim Kaplan;Harald Räcke
中科院分区：
文献类型：
--
作者：
Y. Azar;Edith Cohen;A. Fiat;Haim Kaplan;Harald Räcke
Racke的最新开创性结果是，对于任何网络，都有一种忽略的路由算法，在拥塞方面具有polygog竞争比。不幸的是，Racke的构造不是多项式时间。我们给出一个多项式时间构造
A recent seminal result of Racke is that for any network there is an oblivious routing algorithm with a polylog competitive ratio with respect to congestion. Unfortunately, Racke's construction is not polynomial time. We give a polynomial time constructio