The complexity of an uncapacitated facility location problem

被引：0

作者：

Yi, Bin ^{[1
]}

Li, Rongheng ^{[1
]}

Chen, Chong ^{[1
]}

Li, Yanni ^{[1
]}

机构：

[1] Hunan Normal Univ, Dept Math, Changsha 410081, Hunan, Peoples R China

来源：

ADVANCING SCIENCE THROUGH COMPUTATION | 2008年

关键词：

heuristic algorithms; computational complexity; facility location;

D O I：

暂无

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

In this paper, assuming that the costs of setting up facilities are zero, we show that the 2-product uncapacitated facility location problem is strong NP-complete when the service costs are assumed to be in the metric space.

引用

页码：81 / 83

页数：3

共 8 条

[1]

[Anonymous], 1999, 40 ANN S FDN COMP SC

[2]

Charikar M., 1999, Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, P1, DOI 10.1145/301250.301257

[3]

FISHER ML, 1978, MATH PROGRAM STUD, V8, P73, DOI 10.1007/BFb0121195

[4]

Garey MR, 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[5] A k-product uncapacitated facility location problem [J].

Huang, Huei-Chuen ;

Li, Rongheng .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2008, 185 (02) :552-562

[6]

JAIN K, 1999, P 40 ANN IEEE S FDN, P2

[7]

Shmoys D., 1997, 29 ACM S THEORY COMP, P265, DOI DOI 10.1145/258533.258600

[8]

ZHANG JW, 2004, 15 ACM SIAM S DISCR

← 1 →