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

Author:

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

Indexed by:

EI Scopus

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:

Budget control Approximation algorithms

Author Community:

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

Reprint Author's Address:

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

Show more details

Related Keywords:

Related Article:

Source :

ISSN: 0302-9743

Year: 2020

Volume: 12290 LNCS

Page: 119-130

Language: English

Cited Count:

WoS CC 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:

Online/Total:477/10701235
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.