Conjunto de núcleos

En geometría computacional , un coreset es un pequeño conjunto de puntos que se aproxima a la forma de un conjunto de puntos más grande, en el sentido de que aplicar alguna medida geométrica a los dos conjuntos (como su volumen mínimo del cuadro delimitador ) da como resultado números aproximadamente iguales. Muchos problemas de optimización geométrica natural tienen coresets que se aproximan a una solución óptima dentro de un factor de $1 +$ $ε$ , que se puede encontrar rápidamente (en tiempo lineal o tiempo casi lineal), y que tienen un tamaño limitado por una función de $1/$ $ε$ independiente del tamaño de entrada, donde $ε$ es un número positivo arbitrario. Cuando este es el caso, se obtiene un esquema de aproximación de tiempo lineal o tiempo casi lineal, basado en la idea de encontrar un coreset y luego aplicar un algoritmo de optimización exacto al coreset. Independientemente de lo lento que sea el algoritmo de optimización exacto, para cualquier elección fija de $ε$ , el tiempo de ejecución de este esquema de aproximación será $O$ $(1)$ más el tiempo para encontrar el coreset. ^[1]^[2]

Referencias

^ Agarwal, Pankaj K. ; Har-Peled, Sariel ; Varadarajan, Kasturi R. (2005), "Aproximación geométrica mediante conjuntos de núcleos", en Goodman, Jacob E. ; Pach, János ; Welzl, Emo (eds.), Combinatorial and Computational Geometry , Mathematical Sciences Research Institute Publications, vol. 52, Cambridge Univ. Press, Cambridge, págs. 1–30, MR 2178310.
^ Nielsen, Frank (2016). "10. Optimización aproximada rápida en dimensiones altas con conjuntos de núcleos y reducción rápida de dimensiones". Introducción a HPC con MPI para ciencia de datos. Springer. págs. 259–272. ISBN 978-3-319-21903-5.