Lesson 19: Network Algorithms and Approximations by Mohammad Hajiaghayi: k-Center and k-Median
Mohammad Hajiaghayi · 71:54 · Watch on YouTube
강의는 두 가지 핵심 클러스터링 목표를 다룹니다: k-center, 모든 점에서 가장 가까운 센터까지의 최대 거리를 최소화하는 것, 그리고 k-median, 이러한 거리의 합(또는 평균)을 최소화하는 것입니다. P = NP가 아닌 한 개선할 수 없는 k-center에 대한 깔끔한 2-근사를 보여줍니다. 그리고 단순한 단일 교환 로컬 탐색이 k-median에 대해 5-근사를 제공함을 증명...