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

Author:

Han, Lu (Han, Lu.) | Xu, Dachuan (Xu, Dachuan.) (Scholars:徐大川) | Xu, Yicheng (Xu, Yicheng.) | Zhang, Dongmei (Zhang, Dongmei.)

Indexed by:

EI Scopus SCIE

Abstract:

In this paper, we consider the tau-relaxed soft capacitated facility location problem (tau-relaxed SCFLP), which extends several well-known facility location problems like the squared metric soft capacitated facility location problem (SMSCFLP), soft capacitated facility location problem (SCFLP), squared metric facility location problem and uncapacitated facility location problem. In the tau-relaxed SCFLP, we are given a facility set F, a client set and a parameter tau >= 1. Every facility i is an element of F has a capacity u(i) and an opening cost f(i), and can be opened multiple times. If facility i is opened l times, this facility can be connected by at most lu(i) clients and incurs an opening cost of l f(i). Every facility-client pair has a connection cost. Under the assumption that the connection costs are non-negative, symmetric and satisfy the tau-relaxed triangle inequality, we wish to open some facilities (once or multiple times) and connect every client to an opened facility without violating the capacity constraint so as to minimize the total opening costs as well as connection costs. As our main contribution, we propose a primal-dual based (3 tau + 1)-approximation algorithm for the tau-relaxed SCFLP. Furthermore, our algorithm not only extends the applicability of the primal-dual technique but also improves the previous approximation guarantee for the SMSCFLP from 11.18 + epsilon to 10.

Keyword:

Relaxed triangle inequality Approximation algorithm Facility location problem Soft capacitated Primal-dual

Author Community:

  • [ 1 ] [Han, Lu]Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China
  • [ 2 ] [Xu, Dachuan]Beijing Univ Technol, Dept Operat Res & Informat Engn, Beijing 100124, Peoples R China
  • [ 3 ] [Xu, Yicheng]Chinese Acad Sci, Shenzhen Inst Adv Technol, Shenzhen 518055, Peoples R China
  • [ 4 ] [Zhang, Dongmei]Shandong Jianzhu Univ, Sch Comp Sci & Technol, Jinan 250101, Peoples R China

Reprint Author's Address:

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

Show more details

Related Keywords:

Source :

JOURNAL OF COMBINATORIAL OPTIMIZATION

ISSN: 1382-6905

Year: 2020

Issue: 3

Volume: 40

Page: 848-860

1 . 0 0 0

JCR@2022

ESI Discipline: MATHEMATICS;

ESI HC Threshold:46

Cited Count:

WoS CC Cited Count: 5

SCOPUS Cited Count: 5

ESI Highly Cited Papers on the List: 0 Unfold All

WanFang Cited Count:

Chinese Cited Count:

30 Days PV: 1

Affiliated Colleges:

Online/Total:89/10588495
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.