Resumo Técnico: Agrupamento Hierárquico F-Clustering: Aproximação e Dureza

1. Definição do Problema

O artigo introduz o Agrupamento Hierárquico F-Clustering (HC-F), uma generalização do problema clássico de Agrupamento Hierárquico. No agrupamento hierárquico padrão, um conjunto de dados (representado como um grafo ponderado $G$) é particionado recursivamente até que cada cluster seja um singleton. A qualidade de uma solução é medida pelo objetivo de Dasgupta, que penaliza o corte de arestas com alta similaridade precocemente (ou seja, quando o tamanho do cluster é grande).

Na variação HC-F, o processo recursivo pode terminar sempre que um cluster pertencer a uma classe de grafos específica $\mathcal{F}$. O objetivo continua sendo minimizar o objetivo de Dasgupta, mas os nós folha da árvore de agrupamento resultante devem ser grafos pertencentes a $\mathcal{F}$, em vez de singletons. Os autores focam em duas escolhas naturais para $\mathcal{F}$:

1. Árvores ($\mathcal{T}$): Clusters que são acíclicos.
2. Grafos de Diâmetro Limitado ($\mathcal{D}_d$): Clusters onde o diâmetro (distância máxima entre quaisquer dois nós) é no máximo $d$.

O artigo assume que $\mathcal{F}$ é uma classe não vazia, fechada sob subgrafos e reconhecível em tempo polinomial.

2. Metodologia e Estrutura

Os autores propõvem um framework geral para aproximar o HC-F para classes de grafos que eles denominam $\alpha(n)$-bem comportadas. A metodologia central baseia-se em uma técnica de "achatamento" (flattening), decompondo o problema hierárquico em uma sequência de problemas de particionamento "planos", guiados por Programação Linear (LP).

2.1 A Condição $\alpha(n)$-Bem Comportada

Uma classe de grafos $\mathcal{F}$ é $\alpha(n)$-bem comportada se o problema associado de Particionamento $p\mathcal{F}$-P ($p\mathcal{F}$-P) admitir:

1. Uma formulação natural de Programação Linear Inteira (ILP) usando variáveis de corte de arestas.
2. Restrições codificadas como restrições do "tipo cobertura" (ex: $\sum_{e \in R} y_e \geq 1$) que garantem que um predicado estrutural $p_\mathcal{F}$ seja satisfeito para um conjunto de terminais.
3. Uma relaxação LP solucionável em tempo polinomial.
4. Um algoritmo de arredondamento que, dado uma solução LP, produz um corte válido com custo no máximo $\alpha(n)$ vezes o custo da LP.

Exemplos de $p\mathcal{F}$-P incluem:

• Conjunto de Arestas de Feedback (FES): Remover arestas para quebrar ciclos através de terminais (relevante para Árvores).
• Min-Multicut (MMC): Desconectar pares específicos de terminais (relevante para Diâmetro Limitado).
• $\rho$-Separador: Particionar o grafo de modo que os componentes contendo terminais tenham peso limitado.

2.2 O Framework Algorítmico

O algoritmo procede em duas fases principais:

Fase 1: Pré-processamento e Relaxação LP
Os autores constroem uma ILP (ILP-HC-F) que codifica a estrutura hierárquica usando variáveis baseadas em níveis.

• Variáveis $y^t_e$ indicam se a aresta $e$ é cortada no nível $t$ (onde os níveis correspondem aos pesos dos clusters).
• Variáveis $x^t_v$ indicam se o vértice $v$ satisfaz o predicado $\mathcal{F}$ no nível $t$.
• A formulação inclui restrições de métricas de espalhamento (adaptadas de Charikar e Chatziafratis) para garantir que os clusters sejam suficientemente separados e restrições de refinamento para manter a estrutura hierárquica.
• A ILP é relaxada para uma LP (LP-HC-F) e resolvida. Um procedimento de arredondamento define $x^t_v = 1$ se $x^t_v \geq 1/2$ e escala as variáveis de aresta $y^t_e$ por 2, gerando uma solução parcialmente integral.

Fase 2: Construção Recursiva
O algoritmo constrói a árvore de agrupamento de cima para baixo:

1. Para um cluster atual $H$, ele identifica os vértices que satisfazem o predicado $\mathcal{F}$ ($X_1$) e aqueles que não satisfazem ($X_0$) em um nível específico $t = w(H)/2$.
2. Corte 1 ($E_F$): Utiliza a solução LP restrita a $X_1$ como guia para o problema $p\mathcal{F}$-P. Um algoritmo de aproximação $\alpha(n)$ para $p\mathcal{F}$-P é executado para cortar arestas, garantindo que os vértices em $X_1$ satisfaçam o predicado.
3. Corte 2 ($E_\rho$): Utiliza a solução LP restrita a $X_0$ como guia para o problema de $\rho$-Separador (com $\rho=1/2$). Um algoritmo de aproximação bicritério (com razão $\beta(n) = O(\log n)$) corta arestas para garantir que os componentes restantes sejam pequenos o suficiente (peso $\leq 2/3$ do pai).
4. A união dos cortes particiona $H$ em componentes menores, que são processados recursivamente.

3. Resultados Principais

3.1 Algoritmos de Aproximação

O teorema principal afirma que, se $\mathcal{F}$ é $\alpha(n)$-bem comportada, existe um algoritmo de $O(\alpha(n) + \beta(n))$-aproximação para HC-F, onde $\beta(n) = O(\log n)$ é a razão de aproximação para o problema do $\rho$-Separador.

Aplicando isso às classes específicas:

• Agrupamento de Árvore Hierárquica (HC-$\mathcal{T}$): Como o problema de Conjunto de Arestas de Feedback admite uma aproximação de $O(\log n \cdot \log \log n)$ via arredondamento de LP, os autores alcançam uma aproximação de $O(\log n \cdot \log \log n)$ para HC-$\mathcal{T}$.
• Agrupamento de Diâmetro Limitado Hierárquico (HC-$\mathcal{D}_d$): Como o problema Min-Multicut admite uma aproximação de $O(\log n)$, os autores alcançam uma aproximação de $O(\log n)$ para HC-$\mathcal{D}_d$.

Estes são apresentados como os primeiros algoritmos de aproximação de tempo polinomial para estas variantes específicas de HC-F.

3.2 Dureza de Aproximação

O artigo estabelece resultados fortes de inaproximabilidade sob a Hipótese de Expansão de Conjuntos Pequenos (SSEH):

• Tanto HC-$\mathcal{T}$ quanto HC-$\mathcal{D}_d$ não podem ser aproximados dentro de qualquer fator constante.
• A prova envolve uma redução de caixa-preta da inaproximabilidade do Agrupamento Hierárquico clássico.
  • Para HC-$\mathcal{D}_d$, a redução anexa gadgets de diâmetro $d$ a cada vértice, forçando o algoritmo a tratar o gadget como um representante do vértice original.
  • Para HC-$\mathcal{T}$, a redução anexa triângulos aos vértices. Os autores utilizam a propriedade de que o custo do Agrupamento Hierárquico ótimo é limitado inferiormente pelo custo do Arranjo Linear Mínimo (MLA), mostrando que este limite inferior também se mantém para as instâncias construídas.

4. Significância e Alegações

O artigo afirma fornecer os primeiros resultados algorítmicos para o problema de Agrupamento Hierárquico F-Clustering. Sua principal contribuição é um framework geral que unifica a aproximação de agrupamento hierárquico em várias classes estruturais, desde que essas classes satisfaçam a condição $\alpha(n)$-bem comportada.

Os autores enfatizam que sua abordagem não se limita a árvores ou grafos de diâmetro limitado, mas aplica-se a qualquer classe onde o correspondente problema de particionamento plano (como Multiway Cut) admita uma formulação ILP natural com garantias de arredondamento comprováveis. Eles observam que melhorar essas razões de aproximação além do fator $O(\log n)$ provavelmente exigiria avanços na aproximação de problemas fundamentais de corte e separação (como Sparsest Cut ou Multicut), que atualmente acredita-se serem difíceis de melhorar.

O trabalho também destaca motivações práticas, como a necessidade de estruturas de agrupamento que parem em componentes "simples" (como diretórios em sistemas de arquivos ou categorias de produtos em e-commerce) em vez de forçar todos os clusters a serem singletons, permitindo assim codificar níveis de granularidade significativos.