Indexed by:
Abstract:
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.
Keyword:
Reprint Author's Address:
Email:
Source :
ISSN: 0302-9743
Year: 2020
Volume: 12290 LNCS
Page: 119-130
Language: English
Cited Count:
SCOPUS Cited Count: 1
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 4
Affiliated Colleges: