A linear time algorithm for the weighted lexicographic rectilinear 1-center problem in the plane

被引：3

作者：

Halman, N ^{[1
]}

机构：

[1] Tel Aviv Univ, Sch Math Sci, IL-69978 Tel Aviv, Israel

来源：

INFORMATION PROCESSING LETTERS | 2003年 / 86卷 / 03期

关键词：

algorithms;

D O I：

10.1016/S0020-0190(02)00489-1

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We present an optimal O(n) time algorithm for the weighted lexicographic rectilinear 1-center problem in the plane and prove that calculating the optimal value of the objective function requires a (n log n) time. (C) 2003 Elsevier Science B.V. All rights reserved.

引用

页码：121 / 128

页数：8

共 12 条

[1]

Blum M., 1973, Journal of Computer and System Sciences, V7, P448, DOI 10.1016/S0022-0000(73)80033-9

[2]

DREZNER Z, 1987, NAV RES LOG, V34, P229, DOI 10.1002/1520-6750(198704)34:2<229::AID-NAV3220340207>3.0.CO

[3]

2-1

[4] ON A MULTIDIMENSIONAL SEARCH TECHNIQUE AND ITS APPLICATION TO THE EUCLIDEAN ONE-CENTER PROBLEM [J].

DYER, ME .

SIAM JOURNAL ON COMPUTING, 1986, 15 (03) :725-738

[5] NUCLEOLUS AS A SOLUTION OF A MINIMIZATION PROBLEM [J].

KOHLBERG, E .

SIAM JOURNAL ON APPLIED MATHEMATICS, 1972, 23 (01) :34-&

[6] THE POWER OF GEOMETRIC DUALITY REVISITED [J].

LEE, DT ;

CHING, YT .

INFORMATION PROCESSING LETTERS, 1985, 21 (03) :117-122

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

MEGIDDO, N .

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

[8] THE WEIGHTED EUCLIDEAN 1-CENTER PROBLEM [J].

MEGIDDO, N .

MATHEMATICS OF OPERATIONS RESEARCH, 1983, 8 (04) :498-504

[9] LINEAR-PROGRAMMING IN LINEAR TIME WHEN THE DIMENSION IS FIXED [J].

MEGIDDO, N .

JOURNAL OF THE ACM, 1984, 31 (01) :114-127

[10] On the lexicographic minimax approach to location problems [J].

Ogryczak, W .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 1997, 100 (03) :566-585

← 1 2 →