Throughput is a main performance objective in communication networks. This paper considers a fundamental maximum throughput routing problem -- the all-or-nothing multicommodity flow (ANF) problem -- in arbitrary directed graphs and in the practically relevant but challenging setting where demands can be (much) larger than the edge capacities. Hence, in addition to assigning requests to valid flows for each routed commodity, an admission control mechanism is required which prevents overloading the network when routing commodities. We make several contributions. On the theoretical side we obtain substantially improved bi-criteria approximation algorithms for this NP-hard problem. We present two non-trivial linear programming relaxations and show how to convert their fractional solutions into integer solutions via randomized rounding. One is an exponential-size formulation (solvable in polynomial time using a separation oracle) that considers a "packing" view and allows a more flexible approach, while the other is a compact (polynomial-size) edge-flow formulation that allows for easy solving via standard LP solvers. We obtain a polynomial-time randomized algorithm that yields an arbitrarily good approximation on the weighted throughput, while violating the edge capacity constraints by only a small multiplicative factor. We also describe a deterministic rounding algorithm by derandomization, using the method of pessimistic estimators. We complement our theoretical results with a proof of concept empirical evaluation.
翻译:通勤是通信网络的一个主要绩效目标。本文认为,在任意定向图表和实际相关但具有挑战性的环境下,需求可能(大大)大于边际能力,因此,除了为每种路线商品的有效流动分配请求外,还需要一种准入控制机制,防止网络在路由商品时超负荷。我们作出了一些贡献。在理论方面,我们为这一NP-硬性问题获得了大大改进的双标准近似算法。我们提出了两个非三线线线编程宽松,并展示了如何通过随机四舍五入将其分解解决方案转换成整形解决方案。一个是指数规模的配方(在多线性时间内,使用分离或骨架),考虑“包装”观点,允许采取更灵活的方法,而另一个是压缩(波度大小)边际流配方,便于通过标准的LP-硬性问题解算器简单解析。我们只能获得一个多线性随机随机缩算法,通过随机的逻辑化方法将分解了我们的多级平级算法,同时通过加权算法解释了我们高端的逻辑限制。