A combinatorial 2.375-approximation algorithm for the facility location problem with submodular penalties

被引：6

作者：

Li, Yu ^{[1
]}

Du, Donglei ^{[2
]}

Xiu, Naihua ^{[1
]}

Xu, Dachuan ^{[3
]}

机构：

[1] Beijing Jiaotong Univ, Sch Sci, Dept Math, Beijing 100044, Peoples R China

[2] Univ New Brunswick, Fac Business Adm, Fredericton, NB E3B 5A3, Canada

[3] Beijing Univ Technol, Dept Appl Math, Beijing 100124, Peoples R China

来源：

THEORETICAL COMPUTER SCIENCE | 2013年 / 476卷

基金：

加拿大自然科学与工程研究理事会;

关键词：

Approximation algorithm; Facility location problem; Linear programming; Submodular function;

D O I：

10.1016/j.tcs.2012.11.037

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We offer the currently best approximation ratio 2.375 for the facility location problem with submodular penalties (FLPSP), improving not only the previous best combinatorial ratio 3, but also the previous best non-combinatorial ratio 2.488. We achieve this improved ratio by combining the primal-dual scheme with the greedy augmentation technique. (C) 2012 Elsevier B.V. All rights reserved.

引用

页码：109 / 117

页数：9

共 13 条

[1] Improved combinatorial algorithms for facility location problems [J].

Charikar, M ;

Guha, S .

SIAM JOURNAL ON COMPUTING, 2005, 34 (04) :803-824

[2]

Charikar M, 2001, SIAM PROC S, P642

[3]

Chudak FA, 2007, PROCEEDINGS OF THE EIGHTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P79

[4] A Primal-Dual Approximation Algorithm for the Facility Location Problem with Submodular Penalties [J].

Du, Donglei ;

Lu, Ruixing ;

Xu, Dachuan .

ALGORITHMICA, 2012, 63 (1-2) :191-200

[5]

Fujishige S, 2005, ANN DISCR MATH, V58, P1

[6] Approximation algorithms for supply chain planning and logistics problems with market choice [J].

Geunes, Joseph ;

Levi, Retsef ;

Romeijn, H. Edwin ;

Shmoys, David B. .

MATHEMATICAL PROGRAMMING, 2011, 130 (01) :85-106

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

Guha, S ;

Khuller, S .

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

[8]

Hayrapetyan A, 2005, P SODA, P933

[9] Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation [J].

Jain, K ;

Vazirani, VV .

JOURNAL OF THE ACM, 2001, 48 (02) :274-296

[10]

Li S, 2011, LECT NOTES COMPUT SC, V6756, P77, DOI 10.1007/978-3-642-22012-8_5

← 1 2 →