The facility location problem with general cost functions

被引：81

作者：

Hajiaghayi, MT ^{[1
]}

Mahdian, M ^{[1
]}

Mirrokni, VS ^{[1
]}

机构：

[1] MIT, Dept Math, Comp Sci Lab, Cambridge, MA 02139 USA

来源：

NETWORKS | 2003年 / 42卷 / 01期

关键词：

approximation algorithms; facility location problem; generalized facility location; concave facility location;

D O I：

10.1002/net.10080

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 [计算机科学与技术];

摘要：

In this paper, we introduce a generalized version of the facility location problem in which the facility cost is a function of the number of clients assigned to the facility. We focus on the case of concave facility cost functions. We observe that this problem can be reduced to the uncapacitated facility location problem. We analyze a natural greedy algorithm for this problem and show that its approximation factor is at most 1.861. We also consider several generalizations and variants of this problem. (C) 2003 Wiley Periodicals, Inc.

引用

页码：42 / 47

页数：6

共 27 条

[1]

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

[2]

Arya V., 2001, 33 ACM S THEORY COMP, P21

[3]

Chudak F., 1999, P 10 ANN ACM SIAM S, P875

[4]

Chudak FA, 1998, LECT NOTES COMPUT SC, V1412, P180

[5]

Chudak FA, 1999, LECT NOTES COMPUT SC, V1610, P99

[6]

CHUDAK FA, 1998, UNPUB IMPROVED APPRO

[7]

Chvatal V., 1979, Mathematics of Operations Research, V4, P233, DOI 10.1287/moor.4.3.233

[8]

An improved approximation ratio for the minimum latency problem [J].

Goemans, M ;

Kleinberg, J .

MATHEMATICAL PROGRAMMING, 1998, 82 (1-2) :111-124

[9]

Hierarchical placement and network design problems [J].

Guha, S ;

Meyerson, A ;

Munagala, K .

41ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2000, :603-612

[10]

Greedy strikes back: Improved facility location algorithms [J].

Guha, S ;

Khuller, S .

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 1999, 31 (01) :228-248

← 1 2 3 →