.png){kind=icon}
Return
A Parameterized Approximation Algorithm for the Chromatic k-Median Problem
.png){kind=icon}
OA
AI
DOI：10.1109/ACCESS.2021.3060422.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
Chromatic k -median is a frequently encountered problem in the determination of the topological structures of chromosomes. This problem considers a set C of colored clients and a set F of facilities located in a metric space, where vertical bar C boolean OR F vertical bar = n . The goal is to open k facilities and assign each client to an opened facility, such that clients with the same color are assigned to different facilities and the sum of the distance from each client to the corresponding facility is minimized. It was known that the chromatic $k$ -median problem is W[2]-hard if parameterized by k. This rules out the probability of obtaining an exact FPT( $k$ )-time algorithm for the problem. In this paper, we give an FPT(k)-time approximation algorithm for chromatic k-median. The algorithm achieves a (3+epsilon)-approximation and runs in (k epsilon(-1}))(O(k))n(O(1)) time. We propose a different random sampling algorithm for opening facilities, which is the crucial step in getting the constant factor parameterized approximation.
Keywords:
Approximation
fixed-parameter tractability
clustering
Journal
IF:
3.6
Papers:
9.8W
Citations:
29.4W
Organization
Cited Papers
.png){kind=icon}
ShareSaveShareSaveShareSave
View more