收录:
摘要:
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.
关键词:
通讯作者信息:
电子邮件地址:
来源 :
ISSN: 0302-9743
年份: 2020
卷: 12290 LNCS
页码: 119-130
语种: 英文
归属院系: