Lesson 20: Network Algorithms and Approximations by Mohammad Hajiaghayi: Metric Facility Location
0:00 · Watch on YouTube
이 강의에서는 메트릭 비용량 제약 없는 시설 입지 문제(UFL)가 상수 근사비를 갖는다는 것을 보여줍니다. LP 반올림을 두 단계로 사용합니다. 먼저 분수 해를 "필터링"하여 모든 클라이언트가 근처 시설에서만 서비스받도록 합니다. 그 다음 삼각 부등식을 사용하여 탐욕적으로 반올림하면 깔끔한 4-근사비를 얻습니다. 강의는 연결된 시설 입지 문제를 소개하면서 끝나는데, 이는 클러스터링을 스...