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

作者:

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

收录:

EI SCIE

摘要:

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.

关键词:

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

作者机构:

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

通讯作者信息:

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

查看成果更多字段

相关关键词:

来源 :

JOURNAL OF COMBINATORIAL OPTIMIZATION

ISSN: 1382-6905

年份: 2020

期: 3

卷: 40

页码: 848-860

1 . 0 0 0

JCR@2022

ESI学科: MATHEMATICS;

ESI高被引阀值:15

JCR分区:3

被引次数:

WoS核心集被引频次: 3

SCOPUS被引频次: 3

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

万方被引频次:

中文被引频次:

近30日浏览量: 2

归属院系:

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