Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Max-min fair distribution of modular network flows on fixed paths

Nilsson, Pål LU and Pioro, Michal LU (2006) 5th International IFIP-TC6 Networking Conference 3976. p.916-927
Abstract
In this paper a new aspect of the classical max-min fairness fixed-path problem is investigated. The considered (multi-criteria) optimization problem is almost identical to the continuous-flow problem, with the additional complicating assumption that flows must be integral. We show that such an extension makes the problem substantially more difficult (in fact NP-hard). Through comparison with the closely related continuous-flow problem, a number of properties for the solution of the extended problem are derived. An algorithm, based on sequential resolution of linear programs, that shows to be useful (produce optimal solutions) for many instances of the considered problem, is given. It follows that this algorithm can be made exact, through... (More)
In this paper a new aspect of the classical max-min fairness fixed-path problem is investigated. The considered (multi-criteria) optimization problem is almost identical to the continuous-flow problem, with the additional complicating assumption that flows must be integral. We show that such an extension makes the problem substantially more difficult (in fact NP-hard). Through comparison with the closely related continuous-flow problem, a number of properties for the solution of the extended problem are derived. An algorithm, based on sequential resolution of linear programs, that shows to be useful (produce optimal solutions) for many instances of the considered problem, is given. It follows that this algorithm can be made exact, through substituting the involved linear programs by mixed-integer programs. (Less)
Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
network optimization, max-min fairness, modular flows
host publication
Networking 2006. Networking Technologies, Services, and Protocols; Performance of Computer and Communication Networks; Mobile and Wireless Communications Systems. Proceedings / Lecture Notes in Computer Science
volume
3976
pages
916 - 927
publisher
Springer
conference name
5th International IFIP-TC6 Networking Conference
conference location
Coimbra, Portugal
conference dates
2006-05-15 - 2006-05-19
external identifiers
  • wos:000238114800076
  • scopus:33745875000
ISSN
0302-9743
1611-3349
ISBN
978-3-540-34192-5
DOI
10.1007/11753810_76
language
English
LU publication?
yes
id
b12134d9-e3da-44e6-93db-37d7ad62f808 (old id 403931)
date added to LUP
2016-04-01 12:25:01
date last changed
2025-01-02 17:10:39
@inproceedings{b12134d9-e3da-44e6-93db-37d7ad62f808,
  abstract     = {{In this paper a new aspect of the classical max-min fairness fixed-path problem is investigated. The considered (multi-criteria) optimization problem is almost identical to the continuous-flow problem, with the additional complicating assumption that flows must be integral. We show that such an extension makes the problem substantially more difficult (in fact NP-hard). Through comparison with the closely related continuous-flow problem, a number of properties for the solution of the extended problem are derived. An algorithm, based on sequential resolution of linear programs, that shows to be useful (produce optimal solutions) for many instances of the considered problem, is given. It follows that this algorithm can be made exact, through substituting the involved linear programs by mixed-integer programs.}},
  author       = {{Nilsson, Pål and Pioro, Michal}},
  booktitle    = {{Networking 2006. Networking Technologies, Services, and Protocols; Performance of Computer and Communication Networks; Mobile and Wireless Communications Systems. Proceedings / Lecture Notes in Computer Science}},
  isbn         = {{978-3-540-34192-5}},
  issn         = {{0302-9743}},
  keywords     = {{network optimization; max-min fairness; modular flows}},
  language     = {{eng}},
  pages        = {{916--927}},
  publisher    = {{Springer}},
  title        = {{Max-min fair distribution of modular network flows on fixed paths}},
  url          = {{http://dx.doi.org/10.1007/11753810_76}},
  doi          = {{10.1007/11753810_76}},
  volume       = {{3976}},
  year         = {{2006}},
}