Show simple item record

Max Flow and Min Cut with bounded-length paths: complexity, algorithms, and approximation

hal.structure.identifier
dc.contributor.authorMahjoub, Ali Ridha*
hal.structure.identifier
dc.contributor.authorMcCormick, S. Thomas*
dc.date.accessioned2010-12-14T13:52:22Z
dc.date.available2010-12-14T13:52:22Z
dc.date.issued2010
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5296
dc.language.isoenen
dc.subjectMin Cuten
dc.subjectMax Flowen
dc.subjectapproximation algorithmsen
dc.subject.ddc003en
dc.titleMax Flow and Min Cut with bounded-length paths: complexity, algorithms, and approximationen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe 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.en
dc.relation.isversionofjnlnameMathematical Programming
dc.relation.isversionofjnlvol124en
dc.relation.isversionofjnlissue1-2en
dc.relation.isversionofjnldate2010
dc.relation.isversionofjnlpages271-284en
dc.relation.isversionofdoihttp://dx.doi.org/10.1007/s10107-010-0366-6en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherSpringeren
dc.subject.ddclabelRecherche opérationnelleen
hal.author.functionaut
hal.author.functionaut


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record