Key points are not available for this paper at this time.
최근 분할에 관한 연구는 조기 분할 크기를 고정하지 않고 잘라낸 엣지의 비용과 분할 크기 사이의 균형을 유지하는 비율 절단 비용 메트릭에 초점을 맞추었습니다. 반복적 접근법과 스펙트럴 접근법을 통한 이원 비율 절단 분할은 더 높은 품질의 분할 결과를 제공했습니다. 이 논문에서는 L-way 분할에 대한 비율 절단 비용 메트릭의 일반화를 제공하고 이 비용 메트릭의 하한을 제공하는 다원 비율 절단 분할에 대한 스펙트럴 접근법을 개발합니다. 우리의 접근법은 그래프의 라플라시안의 k 가장 작은 고유값/고유 벡터 쌍을 찾는 것과 관련이 있습니다. 고유 벡터는 그래프의 n 정점을 k 차원 부분 공간에 임베딩합니다. 우리는 임베딩의 점들을 k개의 분할로 강제하는 시간 및 공간 효율적인 클러스터링 휴리스틱을 고안합니다. 현재 작업에 대한 진전을 표준 벤치마크 실험 결과로 입증합니다.
Chan et al. (Sat,)은 이 질문을 연구했습니다.