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é
Journal nameMathematical Programming
MetadataShow full item record
Abstract (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.
Subjects / KeywordsMin Cut; Max Flow; approximation algorithms
Showing items related by title and author.
Pesneau, Pierre; Mahjoub, Ali Ridha; McCormick, S. Thomas; Fortz, bernard (2006) Article accepté pour publication ou publié