IMPROVED COMPLEXITY-BOUNDS FOR LOCATION-PROBLEMS ON THE REAL LINE

被引：93

作者：

HASSIN, R

TAMIR, A

机构：

[1] Department of Statistics, Raymond and Beverly Sackler, Faculty of Exact Sciences, Tel Aviv University, Ramat-Aviv, Tel Aviv

来源：

OPERATIONS RESEARCH LETTERS | 1991年 / 10卷 / 07期

关键词：

FACILITY LOCATION; CENTER PROBLEMS; MEDIAN PROBLEMS; COMPUTATIONAL COMPLEXITY;

D O I：

10.1016/0167-6377(91)90041-M

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

In this note we apply recent results in dynamic programming to improve the complexity bounds of several median and coverage location models on the real line.

引用

页码：395 / 402

页数：8

共 15 条

[1]

AGGARWAL A, 1989, APPLICATIONS ARRAY S

[2] A DYNAMIC-PROGRAMMING ALGORITHM FOR COVERING PROBLEMS WITH (GREEDY) TOTALLY BALANCED CONSTRAINT MATRICES [J].

BROIN, MW ;

LOWE, TJ .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1986, 7 (03) :348-357

[3]

DASKIN M, IN PRESS OPER RES

[4]

EDELSBRUNNEXR H, 1987, ALGORITHMS COMBINATO

[5] AN O(EVLOGV) ALGORITHM FOR FINDING A MAXIMAL WEIGHTED MATCHING IN GENERAL GRAPHS [J].

GALIL, Z ;

MICALI, S ;

GABOW, H .

SIAM JOURNAL ON COMPUTING, 1986, 15 (01) :120-130

[6]

GALIL Z, 1989, UNPUB LINEAR TIME AL

[7]

HSU WL, 1982, OPER RES LETT, V1, P96

[8]

KLAWE MM, 1989, 8916 U BRIT COL TECH

[9]

Kolen A., 1990, DISCRETE LOCATION TH

[10] THE MAXIMUM COVERAGE LOCATION PROBLEM [J].

MEGIDDO, N ;

ZEMEL, E ;

HAKIMI, SL .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1983, 4 (02) :253-261

← 1 2 →