• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

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

Thumbnail
Date
2010
Dewey
Recherche opérationnelle
Sujet
Min Cut; Max Flow; approximation algorithms
Journal issue
Mathematical Programming
Volume
124
Number
1-2
Publication date
2010
Article pages
271-284
Publisher
Springer
DOI
http://dx.doi.org/10.1007/s10107-010-0366-6
URI
https://basepub.dauphine.fr/handle/123456789/5296
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Mahjoub, Ali Ridha
McCormick, S. Thomas
Type
Article accepté pour publication ou publié
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.