• 综合
  • 标题
  • 关键词
  • 摘要
  • 学者
  • 期刊-刊名
  • 期刊-ISSN
  • 会议名称
搜索

作者:

Xu, Yicheng (Xu, Yicheng.) | Xu, Dachuan (Xu, Dachuan.) (学者:徐大川) | Zhang, Yong (Zhang, Yong.) (学者:张勇) | Zou, Juan (Zou, Juan.)

收录:

CPCI-S EI Scopus

摘要:

We consider the universal facility location that extends several classical facility location problems like the incremental-cost facility location, concave-cost facility location, hard-capacitated facility location, soft-capacitated facility location, and of course, uncapacitated facility location. In this problem we are given a set of facilities F and clients C, as well as the distances between any pair of facility and client. Each facility i has its specific cost function fi(·) depending on the amount of clients assigned to that facility. The goal is to assign the clients to facilities such that the sum of facility and service costs is minimized. In metric facility location, the service cost is proportional to the distance between the client and its assigned facility. We study a cost measure known as l22 considered by Jain and Vazirani [J. ACM’01] and Fernandes et al. [Math. Program.’15] where the service cost is proportional to the squared distance. We extend their work to include the aforementioned variants of facility location. As our main contribution, a local search based (11.18 + Ε)-approximation algorithm is proposed. © Springer Nature Switzerland AG 2019.

关键词:

Cost functions Combinatorial mathematics Location Approximation algorithms

作者机构:

  • [ 1 ] [Xu, Yicheng]Chinese Academy of Sciences, Shenzhen Institutes of Advanced Technology, Shenzhen; 518055, China
  • [ 2 ] [Xu, Dachuan]Department of Operations Research and Scientific Computing, Beijing University of Technology, Beijing; 100124, China
  • [ 3 ] [Zhang, Yong]Chinese Academy of Sciences, Shenzhen Institutes of Advanced Technology, Shenzhen; 518055, China
  • [ 4 ] [Zou, Juan]School of Mathematical Sciences, Qufu Normal University, Qufu; Shandong; 273165, China

通讯作者信息:

  • 张勇

    [zhang, yong]chinese academy of sciences, shenzhen institutes of advanced technology, shenzhen; 518055, china

电子邮件地址:

查看成果更多字段

相关关键词:

来源 :

ISSN: 0302-9743

年份: 2019

卷: 11653 LNCS

页码: 591-602

语种: 英文

被引次数:

WoS核心集被引频次: 0

SCOPUS被引频次:

ESI高被引论文在榜: 0 展开所有

万方被引频次:

中文被引频次:

近30日浏览量: 4

在线人数/总访问数:142/3904475
地址:北京工业大学图书馆(北京市朝阳区平乐园100号 邮编:100124) 联系我们:010-67392185
版权所有:北京工业大学图书馆 站点建设与维护:北京爱琴海乐之技术有限公司