A simple dual ascent algorithm for the multilevel facility location problem

被引：0

作者：

Bumb, A ^{[1
]}

Kern, W ^{[1
]}

机构：

[1] Univ Twente, Fac Math Sci, NL-7500 AE Enschede, Netherlands

来源：

APPROXIMATION, RANDOMIZATION, AND COMBINATORIAL OPTIMIZATION: ALGORITHMS AND TECHNIQUES | 2001年 / 2129卷

关键词：

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present a simple dual ascent method for the multilevel facility location problem which finds a solution within 6 times the optimum for the uncapacitated case and within 12 times the optimum for the capacitated one. The algorithm is deterministic and based on the primal-dual technique.

引用

页码：55 / 62

页数：8

共 7 条

[1] A 3-approximation algorithm for the k-level uncapacitated facility location problem [J].

Aardal, K ;

Chudak, FA ;

Shmoys, DB .

INFORMATION PROCESSING LETTERS, 1999, 72 (5-6) :161-167

[2]

Cornuejols G, 1990, DISCRETE LOCATION TH, P119

[3]

Guha Sudipto., 1998, SODA '98: Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, P649

[4]

JAIN K, 1999, P 40 ANN IEEE S FDN

[5]

MEYERSON A, 2000, P 41 IEEE S FDN COMP

[6]

Shmoys D.B., 1997, P 29 ANN ACM S THEOR, V29, P265, DOI DOI 10.1145/258533.258600

[7]

SVIRIDENKO MI, 1997, COMMUNICATION

← 1 →