Clustering de Correlación Totalmente Dinámico: Rompiendo la 3-Aproximación

Estudiamos el clásico clustering de correlación en un entorno dinámico. Dados n objetos y una etiquetación completa de los pares de objetos como similares o disimilares, el objetivo es particionar los objetos en un número arbitrario de clústeres mientras se minimizan los desacuerdos con las etiquetas. En el entorno dinámico, una actualización consiste en un cambio de etiqueta de un borde. En un resultado revolucionario, BDHSS, FOCS'19 mostró cómo mantener una 3-aproximación con tiempo de actualización polilogarítmico proporcionando una implementación dinámica del algoritmo de ACN, STOC'05. Desde entonces, ha sido un problema importante no resuelto determinar si la barrera de 3-aproximación puede ser superada en un entorno totalmente dinámico. En este artículo, resolvemos este problema. Nuestro algoritmo, mejora localmente la salida de al mover algunos vértices a otros clústeres existentes o nuevos clústeres individuales. Presentamos un análisis que demuestra que esta modificación realmente mejora la aproximación a menos de 3. También mostramos que su salida puede mantenerse en un tiempo polilogarítmico por actualización.