Max Flow and Min Cut with bounded-length paths: complexity, algorithms, and approximation
Mahjoub, Ali Ridha; McCormick, S. Thomas (2010), Max Flow and Min Cut with bounded-length paths: complexity, algorithms, and approximation, Mathematical Programming, 124, 1-2, p. 271-284. http://dx.doi.org/10.1007/s10107-010-0366-6
TypeArticle accepté pour publication ou publié
Nom de la revueMathematical Programming
MétadonnéesAfficher la notice complète
Résumé (EN)We consider the “flow on paths” versions of Max Flow and Min Cut when we restrict to paths having at most B arcs, and for versions where we allow fractional solutions or require integral solutions. We show that the continuous versions are polynomial even if B is part of the input, but that the integral versions are polynomial only when B ≤ 3. However, when B ≤ 3 we show how to solve the problems using ordinary Max Flow/Min Cut. We also give tight bounds on the integrality gaps between the integral and continuous objective values for both problems, and between the continuous objective values for the bounded-length paths version and the version allowing all paths. We give a primal–dual approximation algorithm for both problems whose approximation ratio attains the integrality gap, thereby showing that it is the best possible primal–dual approximation algorithm.
Mots-clésMin Cut; Max Flow; approximation algorithms
Affichage des éléments liés par titre et auteur.
Pesneau, Pierre; Mahjoub, Ali Ridha; McCormick, S. Thomas; Fortz, bernard (2006) Article accepté pour publication ou publié