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

author:

Chi, G. (Chi, G..) [1] | Guo, L. (Guo, L..) [2]

Indexed by:

Scopus

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:

approximation algorithm k-center k-median local search

Community:

  • [ 1 ] [Chi G.]Fuzhou University, Fuzhou, China
  • [ 2 ] [Guo L.]Fuzhou University, Fuzhou, China

Reprint 's Address:

Email:

Show more details

Related Keywords:

Related Article:

Source :

ISSN: 0302-9743

Year: 2024

Volume: 14637 LNCS

Page: 173-184

Language: English

0 . 4 0 2

JCR@2005

Cited Count:

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

Online/Total:381/10841966
Address:FZU Library(No.2 Xuyuan Road, Fuzhou, Fujian, PRC Post Code:350116) Contact Us:0591-22865326
Copyright:FZU Library Technical Support:Beijing Aegean Software Co., Ltd. 闽ICP备05005463号-1