The Online Transportation Problem: On the Exponential Boost of One Extra Server
The Online Transportation Problem: On the Exponential Boost of One Extra Server
复制标题
在线传输问题：关于一台额外服务器的指数级提升
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Patchrawat Uthaisombut
中科院分区：
文献类型：
--
作者：
Christine Chung;K. Pruhs;Patchrawat Uthaisombut
当在线算法每个站点具有一台额外的服务器时，我们为在线分离的树上的在线运输问题提供了一种综合性的确定性在线算法。使用度量嵌入产生文献中的结果，然后可以在在线算法每个站点具有一台额外的服务器时，在任意度量空间上在线运输中获取多golog竞争的随机在线算法。
We present a poly-log-competitive deterministic online algorithm for the online transportation problem on hierarchically separated trees when the online algorithm has one extra server per site. Using metric embedding results in the literature, one can then obtain a poly-log-competitive randomized online algorithm for the online transportation on an arbitrary metric space when the online algorithm has one extra server per site.