A flow is said to be confluent if at any node all the flow leaves along a single edge. Given a directed graph G with k sinks and non-negative demands on all the nodes of G, we consider the problem of determining a confluent flow that routes every node demand to some sink such that the maximum congestion at a sink is minimized. Confluent flows arise in a variety of application areas, most notably in networking; in fact, most flows in the Internet are confluent since Internet routing is destination based.We present near-tight approximation algorithms, hardness results, and existence theorems for confluent flows. The main result of this paper is a polynomial-time algorithm for determining a confluent flow with congestion at most 1 + ln(k) in G, if G admits a splittable flow with congestion at most 1. We complement this result in two directions. First, we present a graph G that admits a splittable flow with congestion at most 1, yet no confluent flow with congestion smaller than Hk, thus establishing tight upper and lower bounds to within an additive constant less than 1. Second, we show that it is NP-hard to approximate the congestion of an optimal confluent flow to within a factor of (lg k)/2, thus resolving the polynomial-time approximability to within a multiplicative constant. We also consider a demand maximization version of the problem. We show that if G admits a splittable flow of congestion at most 1, then a variant of the congestion minimization algorithm yields a confluent flow in G with congestion at most 1 that satisfies 1/3 fraction of total demand.We show that the gap between confluent flows and splittable flows is much smaller, if the underlying graph were k connected. In particular, we prove that k-connected graphs with k sinks admit confluent flows of congestion less than C + dmax, where C is the congestion of the best splittable flow, and dmax is the maximum demand of any node in G. The proof of this existence theorem is non-constructive and relies on topological techniques introduced in [16].
展开▼
机译：如果所有流都在单个节点处离开，则称该流是合流的。给定一个有 k 汇的有向图 G ，并且在 G 的所有节点上具有非负需求，我们考虑确定汇合流的问题将每个节点的需求路由到某个接收器，以使接收器中的最大拥塞最小化。汇合的流量出现在各种应用领域，尤其是在网络中。实际上，由于Internet路由是基于目的地的，因此大多数Internet都是汇合的。我们提出了近似紧密的近似算法，硬度结果以及汇合流的存在性定理。本文的主要结果是一种多项式时间算法，如果 G < / I>允许最多1的可分裂流。我们在两个方向上对该结果进行补充。首先，我们给出一个图 G ，该图允许拥塞最多为1的可拆分流，但不存在拥塞小于 H k 的融合流，因此，在加常数小于1的范围内建立了严格的上限和下限。其次，我们证明将最优汇合流的拥塞近似在（lg k ）/ 2，从而将多项式时间近似性解析为一个乘性常数。我们还考虑了问题的需求最大化版本。我们表明，如果 G 允许最多1的可拆分拥塞流，则拥塞最小化算法的一种变体会在 G 中产生最大满足1的拥塞的融合流占总需求的1/3。我们显示，如果基础图连接了 k ，则汇合流和可拆分流之间的差距要小得多。特别地，我们证明具有 k 汇的 k 连通图允许汇合的拥塞流小于 C + d max ，其中 C 是最佳可拆分流的拥塞，而 d max 是最大可拆分流量 G 中的任何节点。该存在性定理的证明是非构造性的，并依赖于[16]中介绍的拓扑技术。
展开▼
