Faster approximation schemes for fractional multicommodity flow problems
Faster approximation schemes for fractional multicommodity flow problems
复制标题
DOI：
10.1145/1328911.1328924
复制
发表时间：
2008-03
期刊：
影响因子：
--
通讯作者：
George Karakostas
中科院分区：
文献类型：
--
作者：
George Karakostas
我们现在完全多项式近似方案运行的并发multicommodity流问题在最短时间依赖大宗商品的数量k。我们表明,通过修改算法,加戈和Konemann[1998]和弗莱舍[2000],我们可以减少运行时间与顶点n和m图边缘从O(ϵ−2 (m2 +公里)),O(ϵ−2平方米)隐式表示的输出,或O(ϵ−2 (m2 + kn的显式表示,其中Õ(f)表示数量为0 （f logO(1)m）。隐式表示包括一组以源为根的树（每个源可以有多个树），并将汇作为它们的叶子，以及从源到特定树中汇的流的流值。鉴于这种隐式表示，并发流量的近似值是已知的，但如果我们想要每条边每个商品的显式流量，我们将不得不将所有这些树组合在一起，这样做的成本可能会令人望而却步。如果我们想要显式地计算解决方案流，我们修改我们的方案，使它们在nk （n是网络中的节点数）中以多对数的方式运行。这是在时间Ω（nk）的琐碎下界的多对数因子范围内，需要在n个节点的网络中明确地写下k个商品的多商品流。因此，我们的方案在运行时间对商品k数量的最小可能依赖关系的多对数因子范围内。
We present fully polynomial approximation schemes for concurrent multicommodity flow problems that run in time of the minimum possible dependencies on the number of commodities k. We show that by modifying the algorithms by Garg and Könemann [1998] and Fleischer [2000], we can reduce their running time on a graph with n vertices and m edges from Õ(ϵ−2(m2 + km)) to Õ(ϵ−2m2) for an implicit representation of the output, or Õ(ϵ−2(m2 + kn for an explicit representation, where Õ(f) denotes a quantity that is O(f logO(1)m). The implicit representation consists of a set of trees rooted at sources (there can be more than one tree per source), and with sinks as their leaves, together with flow values for the flow directed from the source to the sinks in a particular tree. Given this implicit representation, the approximate value of the concurrent flow is known, but if we want the explicit flow per commodity per edge, we would have to combine all these trees together, and the cost of doing so may be prohibitive. In case we want to calculate explicitly the solution flow, we modify our schemes so that they run in time polylogarithmic in nk (n is the number of nodes in the network). This is within a polylogarithmic factor of the trivial lower bound of time Ω(nk) needed to explicitly write down a multicommodity flow of k commodities in a network of n nodes. Therefore our schemes are within a polylogarithmic factor of the minimum possible dependencies of the running time on the number of commodities k.