A unified dual-fitting approximation algorithm for the facility location problems with linear/submodular penalties - Details

Author：

Li, Yu (Li, Yu.) | Du, Donglei (Du, Donglei.) | Xiu, Naihua (Xiu, Naihua.) | Xu, Dachuan (Xu, Dachuan.) (Scholars：徐大川)

Indexed by：

EI Scopus SCIE

Abstract：

In　this　paper,　we　study　two　variants　of　the　classical　facility　location　problem,　namely,　the　facility　location　problem　with　linear　penalties　(FLPLP)　and　the　facility　location　problem　with　submodular　penalties　(FLPSP),　respectively.　We　give　a　unified　dual-fitting　based　approximation　algorithm　for　these　two　problems,　yielding　approximation　ratios　2　and　3　respectively.

Keyword：

Facility location problem Approximation algorithm Submodular function Linear programming

Author Community：

[ 1 ] [Li, Yu]Beijing Jiaotong Univ, Sch Sci, Dept Math, Beijing 100044, Peoples R China
[ 2 ] [Xiu, Naihua]Beijing Jiaotong Univ, Sch Sci, Dept Math, Beijing 100044, Peoples R China
[ 3 ] [Du, Donglei]Univ New Brunswick, Fac Business Adm, Fredericton, NB E3B 5A3, Canada
[ 4 ] [Xu, Dachuan]Beijing Univ Technol, Dept Appl Math, Beijing 100124, Peoples R China

Reprint Author's Address：

徐大川
[Xu, Dachuan]Beijing Univ Technol, Dept Appl Math, 100 Pingleyuan, Beijing 100124, Peoples R China

Email：

liyubjut@gmail.com |
ddu@unb.ca |
nhxiu@center.njtu.edu.cn |
xudc@bjut.edu.cn

Show more details

Related Keywords：

A combinatorial 2.375-approximation algorithm for the facility location problem with submodular penalties
2013，THEORETICAL COMPUTER SCIENCE
A Primal-Dual Approximation Algorithm for the Facility Location Problem with Submodular Penalties
2012，ALGORITHMICA
An Approximation Algorithm For The Stochastic Fault-tolerant Facility Location Problem
2011，10th International Symposium on Operations Research and Its Applications in Engineering, Technology and Management (ISO-RA)
Approximation Algorithms for the Robust Facility Location Problem with Penalties
2015，3rd World Congress of Global Optimization (WCGO)

Source ：

JOURNAL OF COMBINATORIAL OPTIMIZATION

ISSN： 1382-6905

Year： 2014

Issue： 3

Volume： 27

Page： 609-620

1 . 0 0 0

JCR@2022

ESI Discipline： MATHEMATICS;

ESI HC Threshold：81

JCR Journal Grade：2

CAS Journal Grade：3

Cited Count：

WoS CC Cited Count： 1

SCOPUS Cited Count： 2

ESI Highly Cited Papers on the List： 0 Unfold All

WanFang Cited Count：

Chinese Cited Count：

30 Days PV： 3

Affiliated Colleges：

Get Fulltext

DOI Library Discovery Baidu Scholar Search Web of Science

Type
Departments

All Years Choose Year From to