Online Multi-Commodity Flow with High Demands
Online Multi-Commodity Flow with High Demands
复制标题
DOI：
10.1007/978-3-642-38016-7_3
复制
发表时间：
2012-01
期刊：
影响因子：
--
通讯作者：
G. Even;Moti Medina
中科院分区：
文献类型：
--
作者：
G. Even;Moti Medina
本文讨论了在线计算最大效益多商品流（onmcf）的问题，其中流的需求可能大于网络的边缘容量，我们提出了一个在线的、确定性的、集中式的、全有或全无的双准则算法。该算法的竞争比是常数，该算法的能力增加了最多一个对数因子。该算法可以处理两种类型的流请求：（i）低需求的请求，必须沿着路径路由，（ii）高需求的请求，可以使用多路径流路由。两个扩展进行了讨论：请求与已知的持续时间和机器调度。
This paper deals with the problem of computing, in an online fashion, a maximum benefit multi-commodity flow (onmcf), where the flow demands may be bigger than the edge capacities of the network.We present an online, deterministic, centralized, all-or-nothing, bi-criteria algorithm. The competitive ratio of the algorithm is constant, and the algorithm augments the capacities by at most a logarithmic factor.The algorithm can handle two types of flow requests: (i) low demand requests that must be routed along a path, and (ii) high demand requests that may be routed using a multi-path flow.Two extensions are discussed: requests with known durations and machine scheduling.