A Constant Approximation for Maximum Throughput Multicommodity Routing And Its Application to Delay-Tolerant Network Scheduling
Mengxue Liu, Andréa W. Richa, Matthias Rost, Stefan Schmid · 2019
This paper considers the following fundamental maximum throughput routing problem: given a set of k (splittable) multicommodity flows with equal demands in an n-node network, select and route a subset of flows such that the total number of commodities routed that satisfy their demands (i.e., the allor-nothing throughput) is maximized. Our main contribution is the first constant (i.e., independent of k and n) through-putapproximation algorithm for this NP-hard problem, with sublin-ear, namely Õ(√k), edge capacity violation ratio. Our algorithm is based on a clever application of randomized rounding. We also present an interesting application of our result in the context of delay-tolerant network scheduling. We complement our theoretical contribution with extensive simulation in two different scenarios, and find that our algorithm performs significantly better than predicted in theory, achieving an edge capacity violation ratio of at most 3.