A polynomial algorithm for solving a general max-min fairness problem

被引：13

作者：

Tomaszewski, A ^{[1
]}

机构：

[1] Warsaw Univ Technol, Inst Telecommun, PL-00665 Warsaw, Poland

来源：

EUROPEAN TRANSACTIONS ON TELECOMMUNICATIONS | 2005年 / 16卷 / 03期

关键词：

D O I：

10.1002/ett.1047

中图分类号：

TN [电子技术、通信技术];

学科分类号：

0809 ;

摘要：

An iterative algorithm of polynomial complexity is presented that solves a max-min fairness problem which is often encountered while dealing with traffic routing or capacity allocation problems. The algorithm does not depend on any specific traffic routing problem formulation and is sufficiently general to be applied to a broad class of traffic routing and capacity allocation problems. The correctness of the algorithm and its complexity are formally proved. Copyright (c) 2005 AElT.

引用

页码：233 / 240

页数：8

共 9 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2]

BEHRINGER FA, 1981, EUR J OPER RES, V7, P274, DOI 10.1016/0377-2217(81)90349-0

[3]

Bertsekas D., 1987, DATA NETWORKS

[4]

Kelly FP, 1998, J OPER RES SOC, V49, P237, DOI 10.1038/sj.jors.2600523

[5]

KLEINBERG J, 2000, P 35 ANN S FDN COMP

[6] LEXICOGRAPHIC OPTIMALITY IN THE MULTIPLE OBJECTIVE LINEAR-PROGRAMMING - THE NUCLEOLAR SOLUTION [J].

MARCHI, E ;

OVIEDO, JA .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1992, 57 (03) :355-359

[7]

NACE D, 2002, P 7 IEEE INT S COMP, P1530

[8]

OGRYCZAK W, 2002, EUROPEAN J OPERATION, V148, P80

[9]

PIORO M, 2003, P 8 IEEE INT S COMP

← 1 →