2026-07-23T20:32:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24927 2026-02-09T08:02:10Z ddc:004 open_access

Traffic-Oblivious Multi-Commodity Flow Network Design Chimani, Markus Ilsen, Max Multi-commodity flow Digraphs LP-rounding Approximation algorithm We consider the Minimum Multi-Commodity Flow Subgraph (MMCFS) problem: given a directed graph G with edge capacities cap and a retention ratio α ∈ (0,1), find an edge-wise minimum subgraph G' ⊆ G such that for all traffic matrices T routable in G using a multi-commodity flow, α⋅ T is routable in G'. This natural yet novel problem is motivated by recent research that investigates how the power consumption in backbone computer networks can be reduced by turning off connections during times of low demand without compromising the quality of service. Since the actual traffic demands are generally not known beforehand, our approach must be traffic-oblivious, i.e., work for all possible sets of simultaneously routable traffic demands in the original network. In this paper we present the problem, relate it to other known problems in literature, and show several structural results, including a reformulation, maximum possible deviations from the optimum, and NP-hardness (as well as a certain inapproximability) already on very restricted instances. The most significant contribution is a max(1/α, 2)-approximation based on a surprisingly simple LP-rounding scheme. We also give instances where this worst-case approximation ratio is met and thus prove that our analysis is tight. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Markus Chimani and Max Ilsen 2025 Is Part Of LIPIcs, Volume 359, 36th International Symposium on Algorithms and Computation (ISAAC 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2025.19 urn:nbn:de:0030-drops-249273 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2025.19 eng https://creativecommons.org/licenses/by/4.0/legalcode