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

author:

Chi, Gaojie (Chi, Gaojie.) [1] | Guo, Longkun (Guo, Longkun.) [2] (Scholars:郭龙坤)

Indexed by:

CPCI-S EI 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 + 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:

approximation algorithm k-center k-median local search

Community:

  • [ 1 ] [Chi, Gaojie]Fuzhou Univ, Fuzhou, Peoples R China
  • [ 2 ] [Guo, Longkun]Fuzhou Univ, Fuzhou, Peoples R China

Reprint 's Address:

  • [Guo, Longkun]Fuzhou Univ, Fuzhou, Peoples R China;;

Show more details

Version:

Related Keywords:

Related Article:

Online/Total:285/10839413
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