Maximum flow under proportional delay constraint

Abstract : Given a network and a set of source destination pairs (connections), we consider the problem of maximizing the sum of the flow under proportional delay constraints. In this paper, the delay for crossing a link is proportional to the total flow crossing this link. If a connection supports non-zero flow, then the sum of the delays along any path corresponding to that connection must be lower than a given bound. The constraints of delay are on-off constraints because if a connection carries zero flow, then there is no constraint for that connection. The difficulty of the problem comes from the choice of the connections supporting non-zero flow. We first prove a general approximation ratio using linear programming for a variant of the problem. We then prove a linear time 2-approximation algorithm when the network is a path. We finally show a Polynomial Time Approximation Scheme when the graph of intersections of the paths has bounded treewidth.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2017, 689, pp.58-66. 〈10.1016/j.tcs.2017.05.034〉
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01571232
Contributeur : Dorian Mazauric <>
Soumis le : mardi 1 août 2017 - 18:07:03
Dernière modification le : jeudi 11 janvier 2018 - 17:06:45

Fichier

NEW-2-BMV-TCS-short-2016.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Pierre Bonami, Dorian Mazauric, Yann Vaxès. Maximum flow under proportional delay constraint. Theoretical Computer Science, Elsevier, 2017, 689, pp.58-66. 〈10.1016/j.tcs.2017.05.034〉. 〈hal-01571232〉

Partager

Métriques

Consultations de la notice

211

Téléchargements de fichiers

21