.png){kind=icon}
返回
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}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
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.
Keyword:
Approximation
fixed-parameter tractability
clustering
期刊
IF:
3.6
论文数:
9.8W
被引数:
29.4W
机构
引用论文
.png){kind=icon}
分享收藏分享收藏A Computationally Efficient Method to Determine Iron and Magnet Losses in VSI-PWM Fed Axial Flux Permanent Magnet Synchronous Machines一种有效的计算方法来确定vsi-pwm供电的轴向磁通永磁同步电机中的铁和磁体损耗
PREAI
分享收藏
查看更多内容