A new bound and an O(mn) algorithm for the undesirable 1-median problem (maxian) on networks

被引：5

作者：

Colebrook, M ^{[1
]}

Gutiérrez, J ^{[1
]}

Sicilia, J ^{[1
]}

机构：

[1] Univ La Laguna, Fac Matemat, Dept Estad Invest Operat & Computac, Tenerife 38271, Spain

来源：

COMPUTERS & OPERATIONS RESEARCH | 2005年 / 32卷 / 02期

关键词：

network location; undesirable (noxious/obnoxious) facility; maxian problem;

D O I：

10.1016/S0305-0548(03)00238-7

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

The problem of locating an undesirable facility on a network with n nodes and m edges so as to maximize its total weighted distance to all nodes is addressed. We propose a new upper bound to the problem. Likewise, we develop a new algorithm in O(mn) time which dynamically updates this new upper bound. Computational results on low and high dense networks, as well as planar networks, are presented. (C) 2003 Elsevier Ltd. All rights reserved.

引用

页码：309 / 325

页数：17

共 15 条

[1] A note on the location of an obnoxious facility on a network [J].

Berman, O ;

Drezner, Z .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2000, 120 (01) :215-217

[2]

Church R. L., 1978, Transportation Science, V12, P107, DOI 10.1287/trsc.12.2.107

[3] A new algorithm for the undesirable 1-center problem on networks [J].

Colebrook, M ;

Gutiérrez, J ;

Alonso, S ;

Sicilia, J .

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 2002, 53 (12) :1357-1366

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

DYER, ME .

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

[5] ANALYTICAL MODELS FOR LOCATING UNDESIRABLE FACILITIES [J].

ERKUT, E ;

NEUMAN, S .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1989, 40 (03) :275-291

[6] OPTIMUM LOCATIONS OF SWITCHING CENTERS + ABSOLUTE CENTERS + MEDIANS OF GRAPH [J].

HAKIMI, SL .

OPERATIONS RESEARCH, 1964, 12 (03) :450-&

[7]

Hoare C. A. R., 1961, COMMUN ACM, V4, P321, DOI DOI 10.1145/366622.366644

[8] LINEAR-TIME ALGORITHMS FOR LINEAR-PROGRAMMING IN R3 AND RELATED PROBLEMS [J].

MEGIDDO, N .

SIAM JOURNAL ON COMPUTING, 1983, 12 (04) :759-776

[9] An O(mn) algorithm for the 1-maximin problem on a network [J].

Melachrinoudis, E ;

Zhang, FG .

COMPUTERS & OPERATIONS RESEARCH, 1999, 26 (09) :849-869

[10]

MELHORN K, 1999, LEDA PLATFORM COMBIN

← 1 2 →