다층 상관 클러스터링

이 논문에서는 다층 상관 클러스터링을 확립합니다. 이는 상관 클러스터링(Bansal et al., FOCS '02)의 새로운 일반화로 다층 설정에 적용됩니다. 이 모델에서는 공통 집합 V에 대해 상관 클러스터링의 일련의 입력(레이어라고 불림)을 제공합니다. 목표는 불일치 벡터의 ₚ-노름(p 1)을 최소화하는 V의 클러스터링을 찾는 것입니다. 이 불일치 벡터는 각 레이어에 대한 클러스터링의 불일치를 나타내는 요소를 가진 벡터로 정의됩니다. 우리는 먼저 잘 알려진 지역 성장 기법을 기반으로 L이 레이어의 수인 O(L n) 근사 알고리즘을 설계합니다. 그리고 우리는 확률 제약이 있는 문제라는 우리의 문제의 중요한 특수 사례를 연구합니다. 이 경우, 우리는 단일 레이어 경과의 모든 가능한 근사 비율에 대한 (+2) 근사 알고리즘을 먼저 제공합니다. 예를 들어, 일반적으로 =2.5(Ailon et al., JACM '08) 및 비가중치의 경우 =1.73+ (Cohen-Addad et al., FOCS '23)를 사용할 수 있습니다. 더욱이, 우리는 일반 확률 제약 사례에 대한 +2=4.5의 위의 근사 비율을 개선하는 4-근사 알고리즘을 설계합니다. 실제 데이터 세트를 이용한 계산 실험은 우리가 제안한 알고리즘의 효과성을 입증합니다.