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

Author:

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

Indexed by:

CPCI-S EI Scopus

Abstract:

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.

Keyword:

Cost functions Combinatorial mathematics Location Approximation algorithms

Author Community:

  • [ 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

Reprint Author's Address:

  • 张勇

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

Show more details

Related Keywords:

Source :

ISSN: 0302-9743

Year: 2019

Volume: 11653 LNCS

Page: 591-602

Language: English

Cited Count:

WoS CC Cited Count: 0

SCOPUS Cited Count:

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 8

Online/Total:678/10595754
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.