공정한 k-최소-합-반경을 위한 FPT 근사법

우리는 공정성 제약이 있는 k-최소-합-반경(k-MSR) 군집화 문제를 고려한다. k-최소-합-반경 문제는 고전적인 k-중심 및 k-중앙값 문제의 혼합 문제이다. 메트릭 공간 내 점 집합 P와 수 k가 주어지며, 점들을 k개의 군집으로 분할하는 것이 목표이고, 각 군집은 지정된 하나의 중심을 가진다. 최소화하려는 목적은 k개의 군집 반경의 합이다(여기서 k-중심 문제에서는 최대 반경만 고려하고, k-중앙값 문제에서는 개별 점들의 비용 합을 고려한다). 최근 다양한 공정 군집화 개념이 도입되었으며, 우리는 Chierichetti et al. 13에 따른 정의를 따르는데, 이는 군집들의 구성비율이 주어진 민감 속성에 대해 입력 점 집합의 비율을 따라야 함을 요구한다. 민감 속성이 두 가지 값만 가지며 각 값이 입력에 균등하게 분포하는 쉬운 경우에는, 모든 군집이 이 속성에 대해 1:1 비율을 갖는 군집화를 계산하는 것이 목표이다. 이를 1:1 경우라 부른다. 최근 k-MSR 문제에 대해 FPT-근사 알고리즘이 급증했으며, 제약 없는 경우 및 여러 제약 문제 변형을 해결하고 있다. 우리는 여기에 공정성 일반 개념을 만족하는 k-MSR 문제에 대해 (6 + ϵ)-근사를 달성하는 FPT 알고리즘을 설계하여 연구 영역에 기여한다. 특별한 1:1 경우에는 알고리즘을 개선하여 (3 + ϵ)-근사를 달성한다.