집합 커버 문제1 집합 커버(Set Cover) 문제 References Algorithms (Sanjoy Dasgupta) Contents Set Cover (집합 커버) 문제 Approximation Factor 위 이미지에서 점들은 마을을 표현합니다. 여기서 학교를 어디에 배치할 것인가 결정하는데, 두 가지 제한 사항이 있습니다. 각 학교는 마을 내에 위치해야 하고, 학교는 어떤 마을에서도 30마일보다 가까운 곳에 위치해야 합니다. 이 경우 필요한 학교의 최소 갯수는 몇 개 일까요? 이 문제는 전형적인 집합 커버(set cover) 문제입니다. 각 마을 x에 대해, \(S_x\)는 30마일 이내에 있는 마을들의 집합이라고 합시다. x에 있는 학교는 기본적으로 이 집합의 다른 마을들을 커버(cover)합니다. 이때 문제는 '얼마나 많은 집합 \(S_x\.. 2022. 4. 12. 이전 1 다음
