코어셋
Coreset계산 기하학에서 코어 집합은 두 세트(예: 최소 경계 상자 볼륨)에 기하학적 측정을 적용하면 대략 같은 숫자가 나온다는 점에서 더 큰 점 집합의 형태에 근접한 작은 점 집합이다.많은 자연 기하학적 최적화 문제에는 1 + ε의 인자에 대한 최적의 해답에 근사치를 이루는 코어 집합이 있으며, 이러한 코어는 빠르게 찾을 수 있으며(선형 시간 또는 거의 선형에 가까운 시간), 입력 크기와 무관하게 1/2 function의 함수에 의해 경계되는 크기를 가지며, 여기서 ε은 임의의 양의 숫자다.이 경우, 코어셋을 찾은 다음 코어셋에 정확한 최적화 알고리즘을 적용한다는 생각에 기초하여 선형 시간 또는 근 선형 시간 근사 체계를 얻는다.정확한 최적화 알고리즘이 얼마나 느리든 간에, ε의 어떤 고정된 선택에 대해서, 이 근사 계획의 실행 시간은 O(1) + 코어 세트를 찾는 시간이 될 것이다.[1][2]
참조
- ^ Agarwal, Pankaj K.; Har-Peled, Sariel; Varadarajan, Kasturi R. (2005), "Geometric approximation via coresets", in Goodman, Jacob E.; Pach, János; Welzl, Emo (eds.), Combinatorial and Computational Geometry, Mathematical Sciences Research Institute Publications, vol. 52, Cambridge Univ. Press, Cambridge, pp. 1–30, MR 2178310.
- ^ Nielsen, Frank (2016). "10. Fast approximate optimization in high dimensions with core-sets and fast dimension reduction". Introduction to HPC with MPI for Data Science. Springer. pp. 259–272. ISBN 978-3-319-21903-5.
