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 + epsilon, 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 + epsilon at the price of compromising the ratio of radius from 4 to 7.
Keyword:
Reprint 's Address:
Email:
Version:
Source :
THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2024
ISSN: 0302-9743
Year: 2024
Volume: 14637
Page: 173-184
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: 2
Affiliated Colleges: