Resumen Técnico: F-Clustering Jerárquico: Aproximación y Dureza

1. Definición del Problema

El artículo introduce el F-Clustering Jerárquico (HC-F), una generalización del problema clásico de Clustering Jerárquico. En el clustering jerárquico estándar, un conjunto de datos (representado como un grafo ponderado $G$) se particiona recursivamente hasta que cada clúster es un singleton. La calidad de una solución se mide mediante el objetivo de Dasgupta, que penaliza el corte de aristas con alta similitud de forma temprana en la jerarquía (es decir, cuando el tamaño del clúster es grande).

En la variación HC-F, el proceso recursivo tiene permitido terminar siempre que un clúster pertenezca a una clase de grafos específica $\mathcal{F}$. El objetivo sigue siendo minimizar el objetivo de Dasgupta, pero los nodos hoja del árbol de clustering resultante deben ser grafos pertenecientes a $\mathcal{F}$ en lugar de singletons. Los autores se centran en dos elecciones naturales para $\mathcal{F}$:

1. Árboles ($\mathcal{T}$): Clústeres que son acíclicos.
2. Grafos de Diámetro Acotado ($\mathcal{D}_d$): Clústeres donde el diámetro (la distancia máxima entre dos nodos cualesquiera) es a lo sumo $d$.

El artículo asume que $\mathcal{F}$ es una clase no vacía, cerrada bajo subgrafos y reconocible en tiempo polinomial.

2. Metodología y Marco de Trabajo

Los autores proponen un marco general para aproximar el HC-F para clases de grafos que denominan $\alpha(n)$-bien comportadas. La metodología central se basa en una técnica de "aplanamiento", descomponiendo el problema jerárquico en una secuencia de problemas de particionamiento "planos", guiados por Programación Lineal (LP).

2.1 La condición $\alpha(n)$-bien comportada

Una clase de grafos $\mathcal{F}$ es $\alpha(n)$-bien comportada si el problema asociado de Particionamiento $p\mathcal{F}$ ($p\mathcal{F}$-P) admite:

1. Una formulación natural de Programación Lineal Entera (ILP) utilizando variables de corte de aristas.
2. Restricciones codificadas como restricciones de "tipo cobertura" (por ejemplo, $\sum_{e \in R} y_e \geq 1$) que aseguran que un predicado estructural $p_\mathcal{F}$ se satisfaga para un conjunto de terminales.
3. Una relajación LP resoluble en tiempo polinomial.
4. Un algoritmo de redondeo que, dado una solución LP, produce un corte válido con un costo de a lo sumo $\alpha(n)$ veces el costo de la LP.

Ejemplos de $p\mathcal{F}$-P incluyen:

• Conjunto de Edición de Retroalimentación (FES): Eliminar aristas para romper ciclos a través de terminales (relevante para Árboles).
• Min-Multicut (MMC): Desconectar pares específicos de terminales (relevante para Diámetro Acotado).
• $\rho$-Separador: Particionar el grafo de modo que los componentes que contienen terminales tengan un peso acotado.

2.2 El Marco Algorítmico

El algoritmo procede en dos fases principales:

Fase 1: Preprocesamiento y Relajación LP
Los autores construyen un ILP (ILP-HC-F) que codifica la estructura jerárquica utilizando variables basadas en niveles.

• Las variables $y^t_e$ indican si una arista $e$ es cortada en el nivel $t$ (donde los niveles corresponden a los pesos de los clústeres).
• Las variables $x^t_v$ indican si un vértice $v$ satisface el predicado $\mathcal{F}$ en el nivel $t$.
• La formulación incluye restricciones de métricas de propagación (adaptadas de Charikar y Chatziafratis) para asegurar que los clústeres estén suficientemente separados y restricciones de refinamiento para mantener la estructura jerárquica.
• El ILP se relaja a una LP (LP-HC-F) y se resuelve. Un procedimiento de redondeo establece $x^t_v = 1$ si $x^t_v \geq 1/2$ y escala las variables de arista $y^t_e$ por 2, produciendo una solución parcialmente integral.

Fase 2: Construcción Recursiva
El algoritmo construye el árbol de clustering de arriba hacia abajo:

1. Para un clúster actual $H$, identifica los vértices que satisfacen el predicado $\mathcal{F}$ ($X_1$) y aquellos que no lo satisfacen ($X_0$) en un nivel específico $t = w(H)/2$.
2. Corte 1 ($E_F$): Utiliza la solución LP restringida a $X_1$ como guía para el problema $p\mathcal{F}$-P. Se ejecuta un algoritmo de aproximación $\alpha(n)$ para $p\mathcal{F}$-P para cortar aristas, asegurando que los vértices en $X_1$ satisfagan el predicado.
3. Corte 2 ($E_\rho$): Utiliza la solución LP restringida a $X_0$ como guía para el problema del $\rho$-Separador (con $\rho=1/2$). Un algoritmo de aproximación bicriterio (con ratio $\beta(n) = O(\log n)$) corta aristas para asegurar que los componentes restantes sean lo suficientemente pequeños (peso $\leq 2/3$ del padre).
4. La unión de los cortes particiona $H$ en componentes más pequeños, los cuales se procesan recursivamente.

3. Resultados Clave

3.1 Algoritmos de Aproximación

El teorema principal establece que si $\mathcal{F}$ es $\alpha(n)$-bien comportada, existe un algoritmo de $O(\alpha(n) + \beta(n))$-aproximación para HC-F, donde $\beta(n) = O(\log n)$ es el ratio de aproximación para el problema del $\rho$-Separador.

Aplicando esto a las clases específicas:

• Clustering Jerárquico de Árboles (HC-$\mathcal{T}$): Dado que el problema de Conjunto de Edición de Retroalimentación admite una aproximación de $O(\log n \cdot \log \log n)$ vía redondeo de LP, los autores logran una aproximación de $O(\log n \cdot \log \log n)$ para HC-$\mathcal{T}$.
• Clustering Jerárquico de Diámetro Acotado (HC-$\mathcal{D}_d$): Dado que el problema Min-Multicut admite una aproximación de $O(\log n)$, los autores logran una aproximación de $O(\log n)$ para HC-$\mathcal{D}_d$.

Estos se presentan como los primeros algoritmos de aproximación en tiempo polinomial para estas variantes específicas de HC-F.

3.2 Dureza de Aproximación

El artículo establece resultados de inaproximabilidad fuertes bajo la Hipótesis de Expansión de Conjuntos Pequeños (SSEH):

• Tanto HC-$\mathcal{T}$ como HC-$\mathcal{D}_d$ no pueden ser aproximados dentro de cualquier factor constante.
• La prueba implica una reducción de caja negra desde la inaproximabilidad del Clustering Jerárquico clásico.
  • Para HC-$\mathcal{D}_d$, la reducción adjunta gadgets de diámetro $d$ a cada vértice, forzando al algoritmo a tratar el gadget como un representante del vértice original.
  • Para HC-$\mathcal{T}$, la reducción adjunta triángulos a los vértices. Los autores aprovechan la propiedad de que el costo del Clustering Jerárquico óptimo está acotado inferiormente por el costo del Arreglo Lineal Mínimo (MLA), demostrando que este límite inferior también se mantiene para las instancias construidas.

4. Significado y Reivindicaciones

El artículo afirma proporcionar los primeros resultados algorítmicos para el problema de F-Clustering Jerárquico. Su contribución principal es un marco general que unifica la aproximación de clustering jerárquico en diversas clases estructurales, siempre que dichas clases satisfagan la condición de ser $\alpha(n)$-bien comportadas.

Los autores enfatizan que su enfoque no se limita a árboles o grafos de diámetro acotado, sino que se aplica a cualquier clase donde el correspondiente problema de particionamiento plano (como Multiway Cut) admita una formulación ILP natural con garantías de redondeo demostrables. Señalan que mejorar estos ratios de aproximación más allá del factor $O(\log n)$ probablemente requeriría avances en la aproximación de problemas fundamentales de corte y separador (como Sparsest Cut o Multicut), los cuales se cree actualmente que son difíciles de mejorar.

El trabajo también destaca motivaciones prácticas, tales como la necesidad de estructuras de clustering que se detengan en componentes "simples" (como directorios en sistemas de archivos o categorías de productos en comercio electrónico) en lugar de forzar a todos los clústeres a ser singletons, permitiendo así codificar niveles de granularidad significativos.