An approximation algorithm for soft capacitated k-facility location problem

被引：6

作者：

Jiang, Yanjun ^{[1
]}

Xu, Dachuan ^{[1
]}

Du, Donglei ^{[2
]}

Wu, Chenchen ^{[3
]}

Zhang, Dongmei ^{[4
]}

机构：

[1] Beijing Univ Technol, Dept Informat & Operat Res, Coll Appl Sci, 100 Pingleyuan, Beijing 100124, Peoples R China

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

[3] Tianjin Univ Technol, Coll Sci, Tianjin 300384, Peoples R China

[4] Shandong Jianzhu Univ, Sch Comp Sci & Technol, Jinan 250101, Shandong, Peoples R China

来源：

JOURNAL OF COMBINATORIAL OPTIMIZATION | 2018年 / 35卷 / 02期

基金：

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

关键词：

Approximation algorithm; Soft capacitated k-facility location problem; Primal-dual scheme; PLACEMENT;

D O I：

10.1007/s10878-017-0192-3

中图分类号：

TP39 [计算机的应用];

学科分类号：

081203 ; 0835 ;

摘要：

We present a -approximation algorithm for the non-uniform soft capacitated k-facility location problem, violating the capacitated constrains by no more than a factor of 25. The main technique is based on the primal-dual algorithm for the soft capacitated facility location problem, and the exploitation of the combinatorial structure of the fractional solution for the soft capacitated k-facility location problem.

引用

页码：493 / 511

页数：19

共 26 条

[1] Approximation algorithms for hard capacitated k-facility location problems [J].

Aardal, Karen ;

van den Berg, Pieter L. ;

Gijswijt, Dion ;

Li, Shanfei .

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, 2015, 242 (02) :358-368

[2] Improved combinatorial approximation algorithms for the k-level facility location problem [J].

Ageev, A ;

Ye, YY ;

Zhang, JW .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 2004, 18 (01) :207-217

[3]

Aggarwal A, 2010, LECT NOTES COMPUT SC, V6080, P149, DOI 10.1007/978-3-642-13036-6_12

[4]

[Anonymous], 2015, P 26 ANN ACM SIAM S

[5]

[Anonymous], 1997, APPROXIMATION ALGORI

[6] An Approximation Algorithm for Uniform Capacitated k-Median Problem with 1+ε Capacity Violation [J].

Byrka, Jaroslaw ;

Rybicki, Bartosz ;

Uniyal, Sumedha .

INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, IPCO 2016, 2016, 9682 :262-274

[7]

Byrka Jaroslaw, 2015, P 26 ANN ACM SIAM S, P737, DOI DOI 10.1137/1.9781611973730.50

[8]

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

[9] Approximation Algorithms for Soft-Capacitated Facility Location in Capacitated Network Design [J].

Chen, Xujin ;

Chen, Bo .

ALGORITHMICA, 2009, 53 (03) :263-297

[10]

Chuzhoy J, 2005, PROCEEDINGS OF THE SIXTEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P952

← 1 2 3 →