A Parameterized Approximation Algorithm for the Chromatic k-Median Problem

Abstract

Chromatic $k$ -median is a frequently encountered problem in the determination of the topological structures of chromosomes. This problem considers a set $\mathcal {C}$ of colored clients and a set $\mathcal {F}$ of facilities located in a metric space, where $|\mathcal {C}\cup \mathcal {F}|=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