• Complex
  • Title
  • Keyword
  • Abstract
  • Scholars
  • Journal
  • ISSN
  • Conference
搜索

Author:

Wang, Limin (Wang, Limin.) | Zhang, Zhao (Zhang, Zhao.) | Wu, Chenchen (Wu, Chenchen.) | Xu, Dachuan (Xu, Dachuan.) (Scholars:徐大川) | Zhang, Xiaoyan (Zhang, Xiaoyan.)

Indexed by:

CPCI-S EI Scopus SCIE

Abstract:

In this paper, we first consider a dynamic k-level facility location problem, which is a generalization of the k-level facility location problem when considering time factor. We present a combinatorial primal-dual approximation algorithm for this problem which finds a constant factor approximate solution. Then, we investigative the dynamic k-level facility location problem with submodular penalties and outliers, which extend the existing problem on two fronts, namely from static to dynamic and from without penalties (outliers) to penalties (outliers) allowed. Based on primal-dual technique and the triangle inequality property, we also give two constant factor approximation algorithms for the dynamic problem with submodular penalties and outliers, respectively. (C) 2020 Elsevier B.V. All rights reserved.

Keyword:

Submodular penalties Dynamic Primal-dual Facility location Approximation algorithm Outliers

Author Community:

  • [ 1 ] [Wang, Limin]Nanjing Univ, State Key Lab Novel Software Technol, Nanjing 210023, Jiangsu, Peoples R China
  • [ 2 ] [Zhang, Zhao]Zhejiang Normal Univ, Coll Math & Comp Sci, Jinhua 321004, Zhejiang, Peoples R China
  • [ 3 ] [Wu, Chenchen]Tianjin Univ Technol, Coll Sci, Tianjin 300384, Peoples R China
  • [ 4 ] [Xu, Dachuan]Beijing Univ Technol, Dept Operat Res & Informat Engn, Beijing 100124, Peoples R China
  • [ 5 ] [Zhang, Xiaoyan]Nanjing Normal Univ, Sch Math Sci, Nanjing 210023, Jiangsu, Peoples R China
  • [ 6 ] [Zhang, Xiaoyan]Nanjing Normal Univ, Inst Math, Nanjing 210023, Jiangsu, Peoples R China

Reprint Author's Address:

  • [Zhang, Xiaoyan]Nanjing Normal Univ, Sch Math Sci, Nanjing 210023, Jiangsu, Peoples R China;;[Zhang, Xiaoyan]Nanjing Normal Univ, Inst Math, Nanjing 210023, Jiangsu, Peoples R China

Show more details

Related Keywords:

Source :

THEORETICAL COMPUTER SCIENCE

ISSN: 0304-3975

Year: 2021

Volume: 853

Page: 43-56

1 . 1 0 0

JCR@2022

ESI Discipline: COMPUTER SCIENCE;

ESI HC Threshold:87

JCR Journal Grade:4

Cited Count:

WoS CC Cited Count: 0

SCOPUS Cited Count: 8

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 2

Affiliated Colleges:

Online/Total:722/5280142
Address:BJUT Library(100 Pingleyuan,Chaoyang District,Beijing 100124, China Post Code:100124) Contact Us:010-67392185
Copyright:BJUT Library Technical Support:Beijing Aegean Software Co., Ltd.