Indexed by:
Abstract:
Given a set X of n points in a metric space and a radius R, we consider the combining version of k-center and k-median which is with the same objective as k-median, but with the constraint that any x in X is assigned to a center within the range R. In this paper, we propose a bicriteria approximation algorithm achieving a bicriteria approximation ratio of (3+Ε,7), by incorporating local search with the technology of finding key balls with consequent center exchanges therein. Compared to the state-of-the-art approximation ratio of (8, 4) that is based on an LP formulation for k-median, we improve the ratio of the total distance from 8 to 3+Ε at the price of compromising the ratio of radius from 4 to 7. © The Author(s), under exclusive license to Springer Nature Singapore Pte Ltd. 2024.
Keyword:
Reprint 's Address:
Email:
Source :
ISSN: 0302-9743
Year: 2024
Volume: 14637 LNCS
Page: 173-184
Language: English
0 . 4 0 2
JCR@2005
Cited Count:
SCOPUS Cited Count:
ESI Highly Cited Papers on the List: 0 Unfold All
WanFang Cited Count:
Chinese Cited Count:
30 Days PV: 4
Affiliated Colleges: