An approximation algorithm for the dynamic facility location problem with outliers - Details

Author：

Jiang, Yanjun (Jiang, Yanjun.) | Xu, Dachuan (Xu, Dachuan.) (Scholars：徐大川) | Du, Donglei (Du, Donglei.) | Zhang, Dongmei (Zhang, Dongmei.)

Indexed by：

CPCI-S Scopus SCIE

Abstract：

In　this　article,　we　investigate　the　dynamic　(multi-period)　facility　location　problem　with　potentially　unserved　clients　or　outliers.　We　propose　a　3-approximation　primal-dual　algorithm　based　on　an　integer　linear　program　formulation　of　the　problem.　We　further　improve　the　approximation　ratio　to　2　by　combining　the　cost　scaling　and　greedy　improvement　techniques.

Keyword：

Primal-dual Facility location problem Approximation ratio Approximation algorithm

Author Community：

[ 1 ] [Jiang, Yanjun]Beijing Univ Technol, Coll Appl Sci, Dept Informat & Operat Res, 100 Pingleyuan, Beijing 100124, Peoples R China
[ 2 ] [Xu, Dachuan]Beijing Univ Technol, Coll Appl Sci, Dept Informat & Operat Res, 100 Pingleyuan, Beijing 100124, Peoples R China
[ 3 ] [Du, Donglei]Univ New Brunswick, Fac Business Adm, Fredericton, NB E3B 5A3, Canada
[ 4 ] [Zhang, Dongmei]Shandong Jianzhu Univ, Sch Comp Sci & Technol, Jinan 250101, Shandong, Peoples R China

Reprint Author's Address：

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

Email：

jyjmath@emails.bjut.edu.cn |
xudc@bjut.edu.cn |
ddu@unb.ca |
zhangdongmei@sdjzu.edu.cn

Show more details

Related Keywords：

An Approximation Algorithm for the Dynamic k-level Facility Location Problem
2019，13th International Conference on Algorithmic Aspects in Information and Management (AAIM)
A Primal-Dual Approximation Algorithm for the k-Level Stochastic Facility Location Problem
2010，6th International Conference on Algorithmic Aspects in Information and Management
Approximation Algorithms for the Robust Facility Location Problem with Penalties
2015，3rd World Congress of Global Optimization (WCGO)
Approximation Algorithm for the Squared Metric Soft Capacitated Facility Location Problem
2019，8th International Conference on Computational Data and Social Networks (CSoNet)

Source ：

OPTIMIZATION LETTERS

ISSN： 1862-4472

Year： 2019

Issue： 3

Volume： 13

Page： 561-571

1 . 6 0 0

JCR@2022

ESI Discipline： MATHEMATICS;

ESI HC Threshold：54

JCR Journal Grade：2

Cited Count：

WoS CC Cited Count： 1

SCOPUS Cited Count： 1

ESI Highly Cited Papers on the List： 0 Unfold All

WanFang Cited Count：

Chinese Cited Count：

30 Days PV： 6

Affiliated Colleges：

信息科学技术学院本学院/部未明确归属的数据

Get Fulltext

DOI Library Discovery Baidu Scholar Search Web of Science

Type
Departments

All Years Choose Year From to