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

作者:

Han, Lu (Han, Lu.) | Hao, Chunlin (Hao, Chunlin.) | Wu, Chenchen (Wu, Chenchen.) | Zhang, Zhenning (Zhang, Zhenning.)

收录:

EI

摘要:

In this paper, we introduce the lower-bounded knapsack median problem (LB knapsack median). In this problem, we are given a set of facilities, a set of clients, a budget B and a lower bound L. Every facility is associated with a weight. Every facility-client pair is associated with a connection cost. The aim is to select a subset of facilities to open and connect every client to some opened facility, such that the total weights of the selected facilities is no more than B, any opened facility is connected by at least L clients and the total connection costs is minimized. As our main contribution, we study the LB knapsack median and present two approximation algorithms with ratios of 2730 and 1608. The first algorithm is based on reduction and the improved second algorithm is based on an intuitive observation. Additionally, we adapt these two algorithms to the lower-bounded k-median problem (LB k-median) and obtain the approximation ratios of 610 and 387. © 2020, Springer Nature Switzerland AG.

关键词:

Approximation algorithms Budget control

作者机构:

  • [ 1 ] [Han, Lu]Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing; 100190, China
  • [ 2 ] [Hao, Chunlin]Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing; 100124, China
  • [ 3 ] [Wu, Chenchen]College of Science, Tianjin University of Technology, Tianjin; 300384, China
  • [ 4 ] [Zhang, Zhenning]Department of Operations Research and Information Engineering, Beijing University of Technology, Beijing; 100124, China

通讯作者信息:

  • [wu, chenchen]college of science, tianjin university of technology, tianjin; 300384, china

电子邮件地址:

查看成果更多字段

相关关键词:

来源 :

ISSN: 0302-9743

年份: 2020

卷: 12290 LNCS

页码: 119-130

语种: 英文

被引次数:

WoS核心集被引频次:

SCOPUS被引频次: 1

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

万方被引频次:

中文被引频次:

近30日浏览量: 4

归属院系:

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