An improved algorithm for the minmax regret median problem on a tree

被引：37

作者：

Averbakh, I ^{[1
]}

Berman, O

机构：

[1] Univ Toronto, Div Management, Scarborough, ON M1C 1A4, Canada

[2] Univ Toronto, Rotman Sch Management, Toronto, ON M5S 3E6, Canada

来源：

NETWORKS | 2003年 / 41卷 / 02期

关键词：

minmax regret optimization; facility location; polynomial algorithms;

D O I：

10.1002/net.10062

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We consider the 1-median problem with uncertain weights for nodes. Specifically, for each node, only an interval estimate of its weight is known. It is required to find a "minmax regret" location, that is, to minimize the worst-case loss in the objective function that may occur because the decision is made without knowing which state of nature will take place. For this problem on a tree, the best published algorithm has complexity O(n(2)). We present an algorithm with complexity O(n log(2) n). (C) 2003 Wiley Periodicals, Inc.

引用

页码：97 / 103

页数：7

共 15 条

[1] Algorithms for the robust 1-center problem on a tree [J].

Averbakh, I ;

Berman, O .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2000, 123 (02) :292-302

[2] Minmax regret median location on a network under uncertainty [J].

Averbakh, I ;

Berman, O .

INFORMS JOURNAL ON COMPUTING, 2000, 12 (02) :104-110

[3]

BURKARD R, IN PRESS ANN OPER RE

[4] Robust location problems with Pos/Neg weights on a tree [J].

Burkard, RE ;

Dollani, H .

NETWORKS, 2001, 38 (02) :102-113

[5]

Chen BT, 1998, NETWORKS, V31, P93, DOI 10.1002/(SICI)1097-0037(199803)31:2<93::AID-NET4>3.0.CO

[6]

2-E

[7] LINEAR TIME ALGORITHMS FOR 2-VARIABLE AND 3-VARIABLE LINEAR-PROGRAMS [J].

DYER, ME .

SIAM JOURNAL ON COMPUTING, 1984, 13 (01) :31-45

[8]

Goldman A. J., 1971, Transportation Science, V5, P212, DOI 10.1287/trsc.5.2.212

[9] ALGORITHMIC APPROACH TO NETWORK LOCATION PROBLEMS .2. P-MEDIANS [J].

KARIV, O ;

HAKIMI, SL .

SIAM JOURNAL ON APPLIED MATHEMATICS, 1979, 37 (03) :539-560

[10]

Kouvelis P., 1997, ROBUST DISCRETE OPTI

← 1 2 →