Algoritmos de Aproximação para o Problema de Classiﬁcação ...evandro/tese.pdf · sentamos um algoritmo 8logn-aproximado, analisado pela técnica primal-dual, que apesar de

Algoritmos de Aproximação para o Problema deClassificação Métrica

Evandro Cesar Bracht

Dissertação de Mestrado

i

Instituto de ComputaçãoUniversidade Estadual de Campinas

Algoritmos de Aproximação para o Problema de ClassificaçãoMétrica

Evandro Cesar Bracht1

maio de 2004

Banca Examinadora:

• Prof. Dr. Flávio Keidi MiyazawaInstituto de Computação, Unicamp (Orientador)

• Prof. Dr. Orlando LeeInstituto de Computação, Unicamp

• Prof. Dra. Cristina Gomes FernandesInstituto de Matemática e Estatística, USP

• Prof. Dr. Ricardo DahabInstituto de Computação, Unicamp (Suplente)

1Auxílio financeiro do FAPESP

ii

Substitua pela ficha catalográfica

iii

Algoritmos de Aproximação para o Problema de ClassificaçãoMétrica

Este exemplar corresponde à redação final da Dis-sertação devidamente corrigida e defendida porEvandro Cesar Bracht e aprovada pela Banca Ex-aminadora.

Campinas, junho de 2004.

Prof. Dr. Flávio Keidi MiyazawaInstituto de Computação, Unicamp (Orientador)

Dissertação apresentada ao Instituto de Compu-tação,UNICAMP, como requisito parcial para aobtenção do título de Mestre em Ciência da Com-putação.

iv

Substitua pela folha com a assinatura da banca

v

c© Evandro Cesar Bracht, 2005.Todos os direitos reservados.

vi

Nunca desista. Coloque no Easy.(Gregorio Bagio Tramontina)

vii

Resumo

Em um problema de classificação tradicional temos um conjunto den objetos e um conjuntodem classes e queremos classificar cada objeto como pertencentea uma classe, de modo queesta classificação seja consistente com alguns dados que temos sobre o problema. Este trabalhoapresenta um estudo do problema de classificação métrica através de algoritmos aproximados.Os algoritmos aproximados conhecidos para este problema são baseados na solução de grandesprogramas lineares e são impraticáveis para instâncias de tamanho moderado e grande. Apre-sentamos um algoritmo8 log n-aproximado, analisado pela técnica primal-dual, que apesar depossuir fator de aproximação maior que os algoritmos anteriores, pode ser aplicado a grandesinstâncias. Mostramos também que este fator de aproximaçãoé justo, exceto por um fatorconstante. Obtivemos resultados experimentais usando instâncias geradas computacionalmentee instâncias de processamento de imagens com o novo algoritmo e com outros dois algorit-mos baseados na resolução de programas lineares. Para estasinstâncias o algoritmo propostoapresentou soluções de boa qualidade com um ganho considerável no tempo computacional.

viii

Abstract

In a traditional classification problem, we have a set ofn objects and a set ofm labels (orclasses). We wish to assign one ofm labels (or classes) to each one ofn objects, in a way that isconsistent with some observed data that we have about the problem. In this work we present astudy of approximation algorithms for the metric labeling problem. The known approximationalgorithms for this problem are based on solutions of large linear programs and are impracticalfor moderate and large size instances. We present an8 log n-approximation algorithm analyzedby a primal-dual technique which, although has a factor greater than the previous algorithms,can be applied to large sized instances. We also show that theanalysis is tight, up to a constantfactor. We obtained experimental results on computationalgenerated and image processing in-stances with the new algorithm and two other LP-based approximation algorithms. For theseinstances our algorithm presents good quality solutions with a considerable gain of computa-tional time.

ix

Agradecimentos

Primeiramente a Deus, por não deixar faltar força e vontade para que este trabalho se concluísse.Ao professor orientador, Dr. Flávio Keidi Miyazawa, pela convivência sincera e amiga,

apoio constante em todos os momentos, trabalho exímio, paciência e bom humor constante.Aos meus amigos pelo companheirismo, apoio e compreenção. Aalguns amigos em espe-

cial, que estiveram mais próximos durante este tempo, auxiliando no desenvolvimento do tra-balho ou simplesmente companheiros em todos os momentos: Alexandre (Capitão), Gregório,Fernando, Giovani, Luis Augusto, Eduardo (Pará), Silvana,Borin, Juliana... e por aí vai.

A minha família, especialmente a minha mãe Metildes pelo apoio às minhas decisões e porsempre acreditar em mim.

À FAPESP pelo suporte financeiro.A todos aqueles que não impediram a conclusão desse trabalho.

x

Sumário

Resumo viii

Abstract ix

Agradecimentos x

1 Introdução 11.1 Organização da Dissertação . . . . . . . . . . . . . . . . . . . . . . . .. . . . 2

2 Preliminares 42.1 Algoritmos Aproximados . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 4

2.2 O problema de Classificação Métrica . . . . . . . . . . . . . . . . . .. . . . . 6

2.3 Problemas Correlatos . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 9

2.3.1 Problema de Localização de Recursos . . . . . . . . . . . . . . .. . . 9

2.3.2 Problema de Particionamento . . . . . . . . . . . . . . . . . . . . .. 10

2.3.3 Problema de Cobertura por Conjuntos . . . . . . . . . . . . . . .. . . 11

2.4 Diferenças entre o Problema de Classificação Métrica e Problemas Correlatos. 11

3 Algoritmos Baseados em Programação Linear 133.1 Primeiro Programa Linear para o Problema de Classificação Métrica . . . . . . 13

3.1.1 Algoritmo para o caso da métrica uniforme . . . . . . . . . . .. . . . 15

3.1.2 Árvores métricas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

3.1.3 Algoritmo para o caso da métrica geral (Problema ML) . .. . . . . . . 23

3.2 Programação Linear com Interpretação de Fluxo em Rede . .. . . . . . . . . . 35

3.2.1 O caso da métrica uniforme . . . . . . . . . . . . . . . . . . . . . . . 37

3.2.2 O caso da métrica linear . . . . . . . . . . . . . . . . . . . . . . . . . 39

3.2.3 Melhora no fator de aproximação para o caso de distâncias métricaslineares truncadas (TML) . . . . . . . . . . . . . . . . . . . . . . . . . 42

3.2.4 O caso de métricas gerais . . . . . . . . . . . . . . . . . . . . . . . . .52

xi

4 Algoritmo que Utiliza Fluxo em Redes 544.1 Fluxo em Redes e os Problemas de Classificação Métrica . . .. . . . . . . . . 54

4.1.1 O Algoritmo para o Problema TML . . . . . . . . . . . . . . . . . . . 57

5 Algoritmo Guloso para o Problema de Classificação Métrica Uniforme 675.1 Uma Análise Primal-Dual para o Problema de Cobertura porConjuntos . . . . 675.2 O Problema de Localização de Recursos . . . . . . . . . . . . . . . .. . . . . 735.3 Um Algoritmo Primal-Dual para o Problema de Classificação Métrica Uniforme 75

5.3.1 Análise do Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . 785.3.2 Um AlgoritmoASC polinomial para o problema de cobertura por con-

juntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 805.4 O Fator de aproximação éΩ(log n) . . . . . . . . . . . . . . . . . . . . . . . . 82

6 Resultados 866.1 Experimentos Computacionais . . . . . . . . . . . . . . . . . . . . . .. . . . 86

6.1.1 As Instâncias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 876.1.2 Os Testes e Seus Resultados . . . . . . . . . . . . . . . . . . . . . . .88

7 Considerações Finais 967.1 Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 97

Bibliografia 98

xii

Lista de Tabelas

3.1 Os valores dex para uma solução do programa linear (KTR) para a instância dafigura 3.2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3.2 Os valores dex atualizados para a subárvoreT1. . . . . . . . . . . . . . . . . . 28

6.1 Tempos e soluções para os algoritmosAK e GUL com variações no número deobjetos e classes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

6.2 Tempos e soluções para os algoritmosAK e GUL com variações na relaçãoentre o custo de associação e o custo de separação. . . . . . . . . .. . . . . . 95

xiii

Lista de Figuras

2.1 Exemplo de uma instância para o problema de classificaçãométrica. . . . . . . 7

3.1 Algoritmo Alg_UML para o arredondamento da solução do programa linear(KTR) para o problema UML. . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3.2 Exemplo de uma instância. . . . . . . . . . . . . . . . . . . . . . . . . . .. . 163.3 Possíveis situações na escolha deα. . . . . . . . . . . . . . . . . . . . . . . . 173.4 Exemplo de uma árvorer-HST. . . . . . . . . . . . . . . . . . . . . . . . . . . 213.5 Algoritmo para a partição métrica hierárquica. . . . . . . .. . . . . . . . . . . 223.6 Exemplo de uma partição métrica hierárquica. . . . . . . . . .. . . . . . . . . 233.7 Algoritmo para a construção de uma árvorer-HST. . . . . . . . . . . . . . . . 243.8 Algoritmo para o arredondamento da solução do programa linear para o caso

métrico. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273.9 Exemplo de uma instância para o algoritmoAlg_ML. . . . . . . . . . . . . . . 273.10 Custo de associação da instância ilustrada na figura 3.9. . . . . . . . . . . . . . 283.11 Solução do programa linear (KTT) para a instância da figura 3.9. . . . . . . . . 283.12 Modificação em uma árvorer-HST para que todas as classes sejam folhas. . . . 333.13 Algoritmo de Kleinberg e Tardos para o problema de classificação métrica. . . 333.14 Rede de fluxosH(u, v) para uma arestau, v ∈ E. . . . . . . . . . . . . . . . 363.15 Algoritmo para o arredondamento do resultado do programa linear (CKNZ). . . 403.16 Exemplo de valores paraα. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403.17 Grafo para a métrica truncada comM = 5. . . . . . . . . . . . . . . . . . . . 433.18 Algoritmo para o caso das distâncias truncadas utilizando a formulação (CKNZ). 433.19 Links interessantes para o intervaloIℓ . . . . . . . . . . . . . . . . . . . . . . 453.20 Contribuição dolink ua, vb ∈ INT(Iℓ) paraqi = |α(u, i)− α(v, i)|. . . . . . . 483.21 Contribuição dolink ua, vb ∈ CRS(Iℓ) paraqi = |α(u, i)− α(v, i)|. . . . . . 48

4.1 GrafoGL para a métrica truncada do conjunto de classesL comM = 5. . . . . 544.2 Árvore de distâncias truncadas, ondei = r+M . . . . . . . . . . . . . . . . . . 554.3 Possíveis valores dedT (i, j), quandoi e j pertencem a intervalos diferentes. . . 564.4 Algoritmo para o caso das distâncias truncadas de Gupta eTardos. . . . . . . . 57

xiv

4.5 A “corrente” para o vérticeu. . . . . . . . . . . . . . . . . . . . . . . . . . . . 594.6 RedeNI após o acréscimo das arestas que representam o custo de separação. . 604.7 Exemplos de cortes na redeNI . . . . . . . . . . . . . . . . . . . . . . . . . . . 604.8 Exemplo de uma classificaçãof ∗ relacionada a um conjunto de intervalosSr. . 63

5.1 Algoritmo guloso para o problema de cobertura por conjuntos. . . . . . . . . . 685.2 Algoritmo primal-dual para o problema de cobertura por conjuntos. . . . . . . 695.3 Exemplo dos valores deα no momentoαl. . . . . . . . . . . . . . . . . . . . . 705.4 Instância justa para o algoritmoAlg_PDCC. . . . . . . . . . . . . . . . . . . . 715.5 Conjunto de estrelas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . 735.6 Algoritmo guloso para o problema de localização de recursos usando estrelas. . 745.7 Exemplo de estrela de menor custo amortizado. . . . . . . . . .. . . . . . . . 745.8 Uma instância para o problema UML. . . . . . . . . . . . . . . . . . . .. . . 765.9 Todas as estrelas da instância apresentada na figura 5.8.. . . . . . . . . . . . . 765.10 Todos os conjuntos gerados pelas estrelas apresentadas na figura 5.9. . . . . . . 775.11 Novo algoritmo para o problema de classificação métricauniforme. . . . . . . 785.12 Exemplo de um corteC que tem o mesmo custow′

S paraUS = C. . . . . . . . 815.13 Uma instânciaIn. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

6.1 Comparação do tempo de execução dos algoritmos implementados na primeirabateria de testes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

6.2 Comparação do tempo experimental dos algoritmos implementados. . . . . . . 916.3 Imagem com 25% de ruído. Tempo necessário de 4,8 minutos.. . . . . . . . . 936.4 Imagem com 50% de ruído. Tempo necessário de 5,32 minutos. . . . . . . . . 936.5 Imagem com 75% de ruído. Tempo necessário de 8,51 minutos. . . . . . . . . 936.6 Imagem com 100% de ruído. Tempo necessário de 12,22 minutos. . . . . . . . 93

xv

Capítulo 1

Introdução

Quando pensamos em classificação a primeira idéia que surge éque temos um conjuntode objetos e queremos atribuir cada objeto a uma classe de modo que objetos iguais ou muitosimilares pertençam a mesma classe. Na área de computação existem muitos problemas quepossuem uma definição similar, como por exemplo, os problemas de particionamento (cluster-ing) ou o problema de localização de recursos. No entanto, nenhum destes problemas possui asmesmas características do problema de Classificação Métrica.

No problema de classificação métrica temos um conjunto den objetos e um conjunto dem classes e queremos classificar cada objeto como pertencentea uma classe. A escolha damelhor classificação para os objetos leva em consideração dois conjuntos de custos, o custo deatribuição e o custo de separação, que são descritos a seguir.

• Custo de atribuição: é o valor pago por associar um objeto a uma classe. Este valor épago apenas uma vez para cada objeto, porque um objeto só podepertencer a uma classe.

• Custo de separação:No problema de classificação métrica temos informações sobre arelação entre pares de objetos. Quanto mais forte for a relação entre dois objetos, maioré a sua similaridade. Temos também informações sobre a similaridade entre as classes.O custo de separação é pago quando dois objetos, relacionados, são associados a classesdiferentes, sendo que seu valor é proporcional à força da relação existente entre os objetose à dissimilaridade existente entre as classes.

Esta abordagem para o problema de classificação é aplicável avárias áreas, tais como, pro-cessamento de imagens, análise biométrica, visão computacional, etc.

Uma das aplicações na área de processamento de imagens é o problema de restauraçãode imagens degeneradas por ruídos, onde os pontos da imagem são considerados objetos e ascores classes. O custo de associação de uma nova cor a um pontoé definido de acordo coma similaridade entre a nova cor e a cor atual do ponto. Por exemplo, se a cor atual do ponto

1

2 Capítulo 1. Introdução

for 255 e a nova cor for 55, o custo de se associar esta nova cor ao ponto é, digamos, de 200.A relação entre dois pontos, que é um dos fatores do custo de separação, é definida através dacoloração atual destes pontos e a distância entre eles na malha de pontos. Assim seu e v sãodois pontos vizinhos na malha de pontos, e a cor deu é igual a cor dev, então a força da relaçãoentre eles é um valorx muito alto. Se associarmos os objetosu e v a cores diferentes, o custode separação para estes objetos éx vezes a distância entre as cores associadas.

Uma outra aplicação, também em processamento de imagens, é aidentificação de regiõesem uma imagem, onde cada ponto da imagem é visto como um objetoe cada região pode servista como uma classe, assim pontos classificados na mesma classe pertencem à mesma região.

Outro exemplo de aplicação do problema de classificação métrica é o problema de classifi-cação de hipertextos, onde os documentos são os objetos que desejamos classificar e as classessão as categorias. A relação entre os objetos é definida através da existência delinks entre osdocumentos e da ocorrência de palavras chaves em cada documento. O custo de associação deum objeto a uma classe é estimado com base no número de palavras chaves que o documentopossui relacionadas à categoria que a classe representa.

Nesta dissertação estudamos o problema de classificação métrica do ponto de vista de al-goritmos aproximados. Faremos uma breve revisão de alguns conceitos da área de algoritmosaproximados e apresentaremos o problema de classificação métrica e suas variações, junta-mente com algumas abordagens encontradas na literatura. Apresentaremos também, um novoalgoritmo guloso para o problema de classificação uniforme,que surgiu do estudo de proble-mas relacionados, como o problema de localização de recursos e o problema de cobertura porconjuntos.

Este novo algoritmo, apesar de possuir um fator de aproximação maior que o fator de apro-ximação de algoritmos já existentes, tem tempo de execução prático menor e conseqüentementepode ser aplicado a instâncias maiores. Isto ocorre porque agrande maioria dos algoritmos en-contrados na literatura, para o problema de classificação métrica, são baseados na resolução deprogramas lineares grandes.

Apresentaremos também os resultados experimentais comparando tempos de execução equalidade das soluções obtidas para o algoritmo proposto e outros baseados em programaçãolinear.

1.1 Organização da Dissertação

Inicialmente, no capítulo 2, apresentaremos alguns conceitos utilizados na abordagem de algo-ritmos aproximados, passando a seguir para a descrição formal do problema de classificaçãométrica e suas variantes, bem como apresentação de problemas correlatos.

Nos capítulos 3 e 4 são discutidos os principais algoritmos encontrados na literatura para oproblema de classificação métrica, que estão divididos em algoritmos que utilizam programação

1.1. Organização da Dissertação 3

linear, no capítulo 3, e no capítulo 4 algoritmos que utilizam técnicas de fluxo em rede.Além disso, no capítulo 5, apresentamos um novo algoritmo para o problema de classifi-

cação métrica e o seu fator de aproximação, juntamente com alguns problemas que serviram deinspiração para a construção deste algoritmo. Neste capítulo mostraremos também que o fatorde aproximação é justo, exceto por um fator constante.

Por fim, no capítulo 6 é mostrado uma comparação do desempenhodo novo algoritmo como desempenho dos algoritmos apresentados anteriormente.

Capítulo 2

Preliminares

2.1 Algoritmos Aproximados

Nesta seção apresentamos uma visão geral sobre algoritmos de aproximação. Apresentamosuma notação comum na área de algoritmos de aproximação bem como definições e conceitosbásicos. Além disso, discutimos brevemente quais técnicassão utilizadas para se lidar comproblemas de aproximação.

A motivação de se desenvolver algoritmos de aproximação é a de obter algoritmos rápidos(polinomiais), que produzam soluções dentro de um fator de aproximação.

Nos últimos anos, surgiram várias técnicas de caráter geralpara o desenvolvimento de al-goritmos de aproximação. Algumas destas são:arredondamento de soluções via programaçãolinear, dualidade em programação linear e método primal-dual, algoritmos probabilísticos esua desaleatorização, programação semidefinida,dentre outras (veja [5, 12, 22, 23]).

Uma estratégia comum para se tratar problemas de otimizaçãocombinatória é formular oproblema através de um programa linear inteiro e resolver a relaxação linear deste, uma vez queisto pode ser feito em tempo polinomial. A solução obtida através do programa linear pode serfracionária e muitas vezes não é aplicável ao problema. Uma abordagem muito comum nestescasos é o arredondamento das soluções fracionárias geradaspelo programa linear.

Outra técnica, que envolve a formulação do problema como um programa linear, é resolvero sistema dual do programa linear, em vez do primal, e em seguida obter uma solução combase nas variáveis duais. Uma outra técnica mais recente é o uso do método de aproxima-ção primal-dual, que tem sido usado para obter diversos algoritmos combinatórios usando ateoria de dualidade em programação linear. Neste caso, o método é em geral combinatório,não requerendo a resolução de programas lineares e consistede uma generalização do métodoprimal-dual tradicional.

Já no caso de algoritmos probabilísticos, o algoritmo contém passos que dependem de umaseqüência de bits aleatórios, dados na entrada. Neste caso temos um valor esperado para a

4

2.1. Algoritmos Aproximados 5

solução gerada pelo algoritmo que é calculado com base nas probabilidades de todas as esco-lhas aleatórias. É interessante observar que apesar do modelo parecer restrito, a maioria dosalgoritmos probabilísticos podem ser desaleatorizada, através do método das esperanças condi-cionais, tornando-os algoritmos determinísticos (veja [5]). A versão probabilística é em geralmais simples de se implementar e mais fácil de se analisar quea correspondente versão deter-minística. Além disso, muitos dos algoritmos de aproximação combinam o uso de técnicas deprogramação linear com técnicas usadas em algoritmos probabilísticos, considerando o valordas variáveis obtidas pela relaxação linear como probabilidades. Estas técnicas, tanto isolada-mente como em conjunto, têm sido aplicadas com sucesso em diversos problemas nos últimosanos.

Cada algoritmo de aproximação possui um fator de aproximação, que nos diz o quão longepode estar a solução obtida de uma solução ótima. Podemos definir o fator de aproximação paraum algoritmo da seguinte forma.

Definição 2.1.1Dado um algoritmoA para um problema de otimização, seI é uma instân-cia para este problema, denotamos porA(I) o valor da solução devolvida pelo algoritmoAaplicado à instânciaI e denotamos porOPT(I) o correspondente valor para uma soluçãoótima deI. Para problemas de minimização (maximização), diremos queum algoritmoAtem um fator de aproximaçãoα, ou éα-aproximado, seA(I)/OPT(I) ≤ α, comα > 1

(A(I)/OPT(I) ≥ α, comα < 1), para toda instânciaI. No caso dos algoritmos probabilís-ticos, consideramos a desigualdadeE[A(I)]/OPT(I) ≤ α (E[A(I)]/OPT(I) ≥ α), onde aesperançaE[A(I)] é tomada sobre todas as escolhas aleatórias feitas pelo algoritmo.

Para mostrar que um algoritmo é de aproximação, o primeiro passo é buscar uma provade seu fator de aproximação. Posteriormente é interessanteencontrar alguma instância parao algoritmo cujo valor da solução produzida pelo algoritmo atinja o fator de aproximação emrelação ao valor ótimo. Neste caso dizemos que o fator de aproximação do algoritmo é justo.Podemos definir um fator de aproximação justo da seguinte forma.

Definição 2.1.2Dado um algoritmoA, para um problema de minimização (maximização),com fator de aproximaçãoα, dizemos queα é um fator de aproximação justo se existir, paraqualquerǫ ≥ 0, pelo menos uma instânciaI, tal queA(I)/OPT(I) ≤ α−ǫ (A(I)/OPT(I) ≥α + ǫ).

Do ponto de vista teórico os algoritmos de aproximação mais desejados são aqueles que temfator de aproximação próximo de 1, embora isto nem sempre seja possível.

6 Capítulo 2. Preliminares

2.2 O problema de Classificação Métrica

Primeiro, vamos estabelecer algumas convenções básicas denotação. Dada uma funçãoc :

E × E → R que associa um número a cada par de elementosx, y de um conjunto finitoE,denotamos o valor dec em x, y por cxy. Dizemos que uma funçãoc é métrica somente seesta função respeitar a desigualdade triangular, ou seja, dado três elementosx, y e z quaisquer,cxy ≤ cxz + czy. Se uma funçãoc respeitar a desigualdade triangular então,c é métrica.

Podemos definir uma classificação da seguinte forma:

Problema 2.2.1 Classificação é uma função de classificaçãof : P → L, ondeP é um conjuntoden objetos eL é um conjunto dem classes.

No problema de classificação métrica temos um conjuntoP den objetos e um conjuntoLdem classes e o objetivo é associar cada objeto deP a alguma classe emL, de modo que ocusto dessa classificação seja minimizado. Para definir o custo de uma classificação levamosem consideração as seguintes informações:

• Custo de atribuição, definido pela funçãoc : P ×L→ Q+. Quando um objetou ∈ P éassociado a uma classei ∈ L através de uma função de classificaçãof , isto é,f(u) = i,o custoc(u, i) é pago e denotamos porA(u, f) este valor. O custo de atribuição é pagoapenas uma vez para cada objeto, porque um objeto só pode pertencer a uma classe. Ocusto de atribuição total de uma classificaçãof , para todos os objetos emP , éA(P, f) =∑

u∈P A(u, f).

• Distância métrica entre as classes, definida pela funçãod : L × L → Q+, indica adissimilaridade entre as classes, ou seja, quanto maior o valor de d(i, j) parai, j ∈ L

menor é a similaridade entre estas classes.

• Força da relaçãoentre dois objetos, definida pela funçãow : P × P → Q+, que indicaqual a similaridade entre dois objetos, ou seja, quanto maior é o valor dew(u, v) parau, v ∈ P , maior é a similaridade entre estes objetos.

• Custo de separaçãoé o valor pago por associar dois objetosu e v à classes diferentes.Este valor é proporcional à dissimilaridade existente entre as classes e à força da relaçãoentre os objetos. Se o objetou ∈ P for associado à classei ∈ L e o objetov ∈ P forassociado à classej ∈ L através de uma função de classificaçãof , o custo de separaçãopago para os objetosu e v é w(u, v) · d(i, j). Denotamos este valor porS(u, v, f). Ocusto de separação para todos os objetos em P para uma classificaçãof é S(P, f) =∑

u,v∈P S(u, v, f).

Podemos definir o problema de classificação métrica da seguinte forma:

2.2. O problema de Classificação Métrica 7

Problema 2.2.2 Uma instância para o problema de classificação métrica (Metric LabelingProblem (ML)) é uma tupla(P, L, d, c, w) onde

- P é um conjunto den objetos,- L é um conjunto dem classes,- d : L× L→ Q+ é uma função de distância métrica,- c : P × L→ Q+ é o custo de associação,- w : P × P → Q+ é a força da relação entre objetos,

e o objetivo é encontrar uma função de classificaçãof : P → L, tal que,A(u, f) = c(u, f(u))

eS(u, v, f) = w(u, v) · d(f(u), f(v)), e que minimize o custo

Q(f) = A(P, f) + S(P, f) =∑

u∈P

c(u, f(u)) +∑

u,v∈P

w(u, v)d(f(u), f(v)).

Note que podemos interpretar o conjunto de objetosP e o pesow da força da relação entreobjetos como um grafoG = (P, E) com pesos nas arestas, onde o conjunto dos vértices do grafoé composto pelos objetos do conjuntoP e a relação entre dois objetosu, v ∈ P é representadapor uma aresta não orientadae = u, v ∈ E, com pesow(u, v). Daqui em diante podemosreferenciar o pesow(u, v) de uma arestae = u, v comowe.

L

P

i j

u v y

xui xvi xvj

xyj

xyixuj

w(v, y)w(u, v)

w(u, y)

d(i, j)

Figura 2.1: Exemplo de uma instância para o problema de classificação métrica.

A figura 2.1 representa uma instância para o problema de classificação métrica e uma pos-sível classificação seriaf(u) = i, f(v) = j, f(y) = i. Esta classificação teria os seguintescustos:

• custo de classificação:c(u, f(u)) + c(v, f(v)) + c(y, f(y)) = cui + cvj + cyi;

• custo de separação:w(u, v) + w(y, v).


Assim o custo de classificação final seriacui + cvj + cyi + w(u, v) + w(y, v).Esta abordagem do problema de classificação é aplicável a várias áreas, tais como, proces-

samento de imagens, análise biométrica, visão computacional, etc.Um exemplo de aplicação do problema de classificação métricaé a recuperação de imagens

degeneradas por ruídos. Nesta aplicação uma imagem é vista como uma malha de pontos (grid)onde cada ponto possui uma cor, que pode ser sua cor “real” ou oresultando da degeneraçãoda imagem por ruídos. Para o problema de classificação, os pontos são os objetos e as coressão as classes. O objetivo é encontrar a “verdadeira” coloração dos pontos, ou seja, a novaclassificação, que é a imagem sem ruídos.

O custo de associação de um objeto a uma classe é estimado através da coloração atual doobjeto e a cor que a classe representa, e através da posição dedois objetos na malha de pontose suas cores podemos obter a relação entre estes dois objetos.

O objetivo é encontrar a melhor classificação para o conjuntode pontos, onde a “melhorclassificação” é baseada em duas influências competitivas: ocusto de associar uma cor a umponto, e o “castigo” pago por associar dois pontos relacionados, pertencentes a uma mesmaregião da imagem, a cores diferentes. A melhor recuperação da imagem é obtida quando osomatório dos custos de associação com os custos de separação for minimizada.

O problema de classificação métrica possui alguns casos especiais. A principal diferençaentre estes casos está na função de distância aplicada ao conjunto das classes. Podemos citar osseguintes casos especiais:

• Problema de Classificação Métrica Linear (Linear Metric Labeling Problem (LML)):Possui as mesmas características que o problema ML, com a diferença que cada classe édada por um número inteiro positivo não repetido e a função dedistância entre as classesé dada pelo módulo da diferença entre seus números, i.e.,d : L × L → N+ é tal quedij = |i− j|.

• Problema de Classificação Métrica Linear Truncada (Truncated Linear Metric La-beling Problem (TML)): Possui as mesmas características que o problema ML, com adiferença que cada classe é dada por um número inteiro positivo não repetido e a funçãode distância entre as classes é dada pelo menor valor entre o módulo da diferença entre asduas classes e um valor máximoM , i.e.,d : L×L→ N+ satisfazdij = min|i− j|, M.

• Problema de Classificação Uniforme (Uniform Metric Labeling (UML)): Possui as mes-mas características que o problema ML, com a diferença que a função de distância entreas classes sempre devolve 1 para quaisquer duas classes, i.e., dij = 1 ∀i, j ∈ L comi 6= j e 0 caso contrário.

Boykov, Veksler e Zabih [4] desenvolveram a conexão entre o problema de classificaçãométrica uniforme, comm > 2, e o problema de multi-cortes em grafos (multiway cuts) e

2.3. Problemas Correlatos 9

mostraram uma redução direta do problema de multi-cortes para o problema de classificaçãométrica uniforme. Assim, como o problema de multi-cortes é um problema NP-difícil, o pro-blema de classificação métrica uniforme também é.

2.3 Problemas Correlatos

Existem problemas que são muito parecidos com o problema de classificação métrica. Algunsdestes são os problemas de localização de recursos, particionamento, cobertura por conjuntos,entre outros. Devido à grande similaridade existente entreestes problemas e o problema declassificação métrica, muitas das idéias desenvolvidas para estes problemas correlatos podemser úteis para o nosso problema. A seguir descrevemos um pouco mais sobre alguns destesproblemas.

2.3.1 Problema de Localização de Recursos

Desde o início dos anos 60 o problema de localização de recursos (Facility Location Problem)ocupa um ponto central na área de pesquisa operacional. Esteproblema modela situações dedefinição do local de instalação de indústrias, armazéns, escolas, e hospitais e mais recente-mente incluem a instalação de servidores de proxy na web [22], instalação de centrais telefôni-cas, entre outros.

Problema 2.3.1 No Problema de Localização de Recursos temos um conjuntoF = 1, . . . , nde recursos, e um conjuntoC = 1, . . . , m de clientes, que devem ser atendidos pelos re-cursos. Temos também um custocij ∈ Z, onde1 ≤ i ≤ n e 1 ≤ j ≤ m, que representa ocusto de se atender o clientej pelo recursoi. Se algum cliente for associado ao recursoi entãotemos que pagar um custofi para abrir o recursoi. O objetivo do problema é encontrar umsubconjuntoA ⊆ F que minimize o custo de abrir os recursos emA e atender todos os clientes.

O problema de localização de recursos apresenta algumas variantes, e dentre elas podemosdestacar:

• Problema de localização de recursos sem capacidades: Neste problema, um recursonão possui restrições no número máximo de clientes que podemser associados a ele. Istopossibilita, por exemplo, uma solução onde apenas um recurso é aberto para atender todosos clientes.

• Problema de localização de recursos com capacidades: Nesta variante, um recurso temum limite máximo de clientes que podem ser atendidos por ele.


Além das variações de um recurso possuir restrição de capacidade, existem outras variaçõesque dizem respeito ao custo de associar um cliente ao recurso. Estes custos podem ser métricosou não-métrico.

2.3.2 Problema de Particionamento

Particionamento(Clustering)é a arte de encontrar grupos em um dado conjunto de objetos talque os objetos pertencentes ao mesmo grupo são similares entre si, enquanto que objetos emdiferentes grupos são tão diferentes quanto possível [16].

O problema de dividir um conjunto de dados em um número pequeno de partições comitens relacionados tem um papel crucial em muitas aplicações para extração de conhecimento eanálise de dados, tais como busca na web e classificação dos resultados ou interpretação de da-dos experimentais em biologia molecular. Problemas de particionamento são muito estudados,na literatura, onde encontramos um grande número de variantes bem como diversos algoritmos.Além disso, problemas de particionamento aparecem em outras áreas do conhecimento comnomes diferenciados. Por exemplo, em biologia particionamento ficou conhecido como taxo-nomia numérica, em ciências sociais como tipologia, na áreade reconhecimento de padrões (emInteligência Artificial) como aprendizado não supervisionado, em lingüística comoclumping,em geografia como regionalização, em antropologia como serialização, etc.

Em uma definição superficial do problema de particionamento temos um conjunto denpontos, que desejamos particionar em subconjuntos, respeitando certas restrições estruturais doselementos entre e em cada parte, de tal forma que uma dada função objetivo seja minimizada (oumaximizada). Esta função objetivo e as restrições estruturais variam de acordo com a aplicação.

Problema 2.3.2 Uma instância para o problema de particionamento é uma tripla (S, CS, c),onde

- S é um conjunto den objetos,- CS é um conjunto de partições deS, não necessariamente dado de forma explícita,- c : CS → Q+ é uma função de custo de uma partição.

O objetivo é encontrar uma partiçãoC ∈ CS que minimizec(C).

Na análise de dados baseada em partições o objetivo é particionar o conjunto de objetosde maneira que objetos em uma mesma parte sejam mais similares possível, enquanto que emrelação a objetos externos à parte sejam mais diferentes possível. Existem muitas maneiras deformular matematicamente as funções objetivo de diversos problemas de particionamento, queconsiste em buscar a homogeneidade interna à parte e a separação entre partes. Em seguidavamos citar alguns problemas de particionamento mais conhecidos.

• mínimo k-clustering: Possui as mesmas características que o problema 2.3.2 acrescidode uma função de distânciad : S × S → N+ que satisfaz a desigualdade triangular. O

2.4. Diferenças entre o Problema de Classificação Métrica e Problemas Correlatos. 11

objetivo é encontrar uma partição deS emk conjuntos de modo que a maior distância en-tre dois objetos pertencentes a mesma parte seja minimizada. Assim queremos minimizarmaxi∈1,...,k maxx,y∈Ci

d(x, y).

• k-centros: Dado um grafoG = (S, E) com uma funçãod de distância nas arestas, temoscomo objetivo encontrark elementosc1, c2, . . . , ck deS, chamados de centros, onde cadau ∈ S é associado aci sed(u, ci) = min1≤j≤k d(u, cj), definindo assimk partes. O custode um particionamento é dado por

∑k

i=1

∑u∈Ci

d(u,ci), e o objetivo é encontrark centrosque minimizem esta somatória.

2.3.3 Problema de Cobertura por Conjuntos

O problema da cobertura por conjuntos(Set Cover)é um problema muito conhecido em otimiza-ção e surge quando tentamos “adquirir”, de forma eficiente, itens que estão empacotados emum conjunto fixo de pacotes, podendo ter o mesmo item em pacotes diferentes. O objetivo é“adquirir” todos os itens pegando o menor número de pacotes,ou, na versão com pesos, o con-junto de pacotes que contêm todos os itens e seja o de menor custo, se os pacotes tiverem custosde aquisição.

Problema 2.3.3 Uma instância para o problema de Cobertura por Conjuntos Mínima (MinCC)é composta de um conjuntoESC = e1, e2, . . . , en den objetos, uma coleçãoSSC de subcon-juntos deESC, ondeSSC = C1, . . . , Ct, e uma função de custoc : SSC→ Q+. O objetivoé encontrar uma subcoleçãoSSC

′ ⊆ SSC tal que∪Ci∈SSC′Ci = ESC e

∑Ci∈SSC

′ c(Ci) émínimo.

2.4 Diferenças entre o Problema de Classificação Métrica eProblemas Correlatos.

No problema de classificação métrica, quando desejamos classificar um conjunto de objetos,temos que levar em consideração as informações que temos sobre o conjunto de dados, que sãoo relacionamento entre objetos e o relacionamento dos objetos com as possíveis classes. Porexemplo, se no problema de restaurar imagens degeneradas por ruídos a intenção fosse associarum ponto a uma cor, sem observar a relação deste ponto com seusvizinhos, poderíamos mapeareste problema para o problema de localização de recursos, onde os pontos são os clientes, eas cores são os recursos. No entanto, se desejamos simplesmente criar partições baseadas nalocalidade e na cor de cada ponto, ou seja, a informação considerada relevante é a relaçãode um ponto com seus vizinhos, esta abordagem pode ser mapeada como um problema departicionamento.


Ambas as abordagens para o problema de recuperação de imagens levam em consideraçãoapenas parte das informações disponíveis, causando assim uma atribuição de cores inadequadapara os pontos. Quando utilizamos o problema de classificação métrica para modelar a restau-ração de imagens degeneradas por ruídos, obtemos uma modelagem que leva em consideraçãotanto o custo de associar um ponto a uma cor quanto o custo de atribuir cores diferentes a doispontos que pertencem à mesma região da imagem.

Capítulo 3

Algoritmos Baseados em ProgramaçãoLinear

O Problema de Classificação Métrica (ML) foi apresentado pela primeira vez por Kleinberge Tardos [17], que mostram uma formulação do problema de classificação métrica uniformecomo um programa linear inteiro. Mais recentemente, Chekuri et al. [7] apresentaram umprograma linear que é aplicado ao problema de classificação métrica de uma forma mais natural.Apresentamos a seguir estas duas abordagens.

3.1 Primeiro Programa Linear para o Problema de Classifi-cação Métrica

Kleinberg e Tardos [17] apresentaram a primeira formulaçãoem um programa linear para oproblema de classificação métrica uniforme. Posteriormente, esta formulação é adaptada para ocaso geral do problema de classificação métrica.

Como vimos no capítulo 2, podemos interpretar o conjunto de objetosP e a funçãow darelação entre objetos como um grafoG = (P, E) com pesos nas arestas, onde o conjunto dosvértices do grafo é o conjuntoP e a relação entre dois objetosu, v ∈ P é representada por umaaresta não orientadae = u, v ∈ E, com pesowe = w(u, v).

Para definir o programa linear inteiro, Kleinberg e Tardos usaram três tipos de variáveis:

• xui é uma variável binária que indica se o objetou está associado à classei, para cadaobjetou ∈ P e cada classei ∈ L,

• ze é uma variável binária, para cadae = u, v ∈ E, que indica se dois objetos relaciona-dos pela arestae são associados a classes diferentes,

• zei, para cadae = u, v ∈ E e i ∈ L, expressa o valor absoluto dexui − xvi.

13

14 Capítulo 3. Algoritmos Baseados em Programação Linear

A restrição que cada objeto deve ser associado a exatamente uma classe, é dada por

∑

i∈L

xui = 1.

A distância entre as classes associadas a dois objetosu e v, relacionados pela arestae =

u, v ∈ E, no problema de classificação métrica uniforme pode ser expressa em função dasvariáveisxui como

d(f(u), f(v)) =1

2

∑

i∈L

|xui − xvi|.

Para representar esta distância é introduzida a variávelzei, que representa o valor absoluto dexui − xvi. No programa linear, isso é representado pelas restrições

zei ≥ xui − xvi e zei ≥ xvi − xui,

aproveitando que os custos são todos não negativos e a funçãoobjetivo é de minimização.Assim, a variávelze, que representa se dois objetos vão ser separados, é definidapela restrição

ze =1

2

∑

i∈L

zei.

A função objetivo é composta por dois termos, o custo de associação, que é representadopor ∑

u∈P,i∈L

cuixui

e o custo de separação, representado por

∑

e∈E

weze.

Assim, a formulação em programação linear inteira fica:

min∑

e∈E

weze +∑

u∈P,i∈L

cuixui

s.a.∑

i∈L

xui = 1 ∀u ∈ P,

ze =1

2

∑

i∈L

zei ∀ e ∈ E,

zei ≥ xui − xvi ∀ e = u, v ∈ E, ∀ i ∈ L,

zei ≥ xvi − xui ∀ e = u, v ∈ E, ∀ i ∈ L,

xui ∈ 0, 1 ∀ u ∈ P, ∀ i ∈ L.

(KTG)

3.1. Primeiro Programa Linear para o Problema de Classificação Métrica 15

O programa linear relaxado da formulação (KTG) pode ser obtido removendo-se as restri-ções de integralidadexui ∈ 0, 1 e acrescentando-se as restriçõesxui ≥ 0, para todou ∈ P

e i ∈ L. Observe que não é necessário acrescentar a restriçãoxui ≤ 1, visto que o programalinear possui a restrição

∑i∈L xui = 1 que não permite que as variáveisxui assumam valores

maiores que 1. Com essas alterações obtemos a relaxação do programa linear (KTG).

min∑

e=u,v∈E

weze +∑

u∈P,i∈L

cuixui

s.a.∑

i∈L

xui = 1 ∀ u ∈ P,

ze =1

2

∑

i∈L

zei ∀ e ∈ E,

zei ≥ xui − xvi ∀ e = u, v, ∀ i ∈ L,

zei ≥ xvi − xui ∀ e = u, v, ∀ i ∈ L,

xui ≥ 0 ∀ u ∈ P, ∀ i ∈ L,

(KTR)

3.1.1 Algoritmo para o caso da métrica uniforme

Sejax uma solução do programa linear inteiro (KTG). Sexui for igual a1, significa que, levandoem consideração os custos de associação e os custos de separação para o objetou e seus vizi-nhos, uma melhor classificação para o objetou é a classei.

No programa linear relaxado (KTR), a variávelxui pode assumir valor fracionário entre0

e 1. No entanto, relembrando o exemplo de recuperação de imagens degeneradas por ruídos,não podemos dizer que um ponto será30% verde,40% vermelho e30% azul. Então, surge anecessidade de transformar os valores fracionários das variáveisxui em valores inteiros, paratanto, o conteúdo de uma variáveisxui é interpretado como a probabilidade do objetou seratribuído à classei.

Uma primeira idéia que surge é considerar cada variávelxui separadamente, sortear um valoraleatório pertencente ao intervalo[0, 1] e decidir, baseado neste valor aleatório, se aquele objetoserá associado à classe. Entretanto, nesta abordagem pode ocorrer de objetos relacionados, comprobabilidades iguais ou semelhantes, serem separados.

Kleinberg e Tardos [17] apresentam um algoritmo, que denominamos deAlg_UML, itera-tivo dois aproximado para o arredondamento do resultado do programa linear (KTR). Em cadaiteração é escolhida uma classe para ser analisada. Veja o algoritmo na figura 3.1.

Para melhor ilustrar o funcionamento do algoritmoAlg_UML utilizaremos uma instânciapara o problema de classificação métrica uniforme, apresentada na figura 3.2, que contendoduas classes e três objetos. Assumimos a solução apresentada na tabela 3.1 como uma soluçãodo programa linear (KTR) para esta instância, onde o conteúdo da célula na linhau colunai

representa o valor da variávelxui.


ALGORITMO Alg_UML (P, L, d, c, w)

onde(P, L, d, c, w) é uma instância para o problema UML.

1. % Inicialmente nenhum objeto possui uma classe associada

2. Seja(x, z) uma solução para o programa linear (KTR)

3. ExecutaRound_UML(P, L, x)

PROCEDIMENTO Round_UML(P, L, x)

1. U ← P

2. EnquantoU 6= ∅3. Selecione aleatoriamente uma classei ∈ L

4. α← random[0, 1]

5. Para todou ∈ U

6. Seα ≤ xui então

7. f(u)← i

8. U ← U \ u9. Devolvaf

Figura 3.1: AlgoritmoAlg_UMLpara o arredondamento da solução do programa linear (KTR)para o problema UML.

v 2

4

3

15 12 2 610

u y

i j

3

Figura 3.2: Exemplo de uma instância.

i j

u 0,6 0,4v 0,2 0,8y 0,5 0,5

Tabela 3.1: Os valores dex para uma solução do programa linear (KTR) para a instância dafigura 3.2.

Inicialmente o algoritmo seleciona aleatoriamente uma classe e sorteia um valorα no in-tervalo[0, 1]. Vamos assumir quei é a classe selecionada e o valor deα é 0,4. Em seguida, o


algoritmo verifica quais são os objetos não classificados (representados pelo conjuntoU) comvalor xui, u ∈ U , maior queα. Pela tabela 3.1, verificamos que esta condição é satisfeitaparaos objetosu e y. Assim os objetosu e y são associados à classei e removidos do conjuntoU .O algoritmo repete este procedimento até que todos os objetos tenham sido classificados.

Note que a classei pode ser escolhida novamente em uma próxima iteração e ter o objetov

associado à ela, No entanto, é mais provável que o objetov seja associado à classej uma vezquexvi é menor quexvj .

10 xui xvi

α1 α3α2

Figura 3.3: Possíveis situações na escolha deα.

Para compreender melhor a função da variávelα no algoritmoAlg_UML, observe a figura 3.3,onde temos três casos que podem ocorrer em relação ao valor deα e a separação de objetosu ev relacionados:

a) O valor deα ocorre no intervaloα1. Neste caso os objetosu ev são associados à mesmaclasse.

b) O valor deα ocorre no intervaloα2. Neste caso apenas o objetou tem sua classe associadanesta iteração e dizemos queu ev são separados.

c) O valor deα ocorre no intervaloα3. Neste caso os objetosu e v não são associados àclassei nesta iteração.

Os lemas a seguir apresentam propriedades do algoritmo probabilísticoAlg_UML.

Lema 3.1.1 Em uma iteração doEnquantodo procedimento Round_UML, a probabilidade deum objetou ∈ U ser associado a uma classei é precisamentexui/m e a probabilidade deu ser associado a qualquer classe em uma iteração é1/m, ondem é o número de classes.Assim, numa execução do Round_UML, a probabilidade do objeto u ser associado à classei éexatamentexui.

Prova. Pela restrição∑

i∈L xui = 1 temos que a probabilidade de um objetou ser associado aqualquer classe é 1. A probabilidade de uma classe ser escolhida é1/m. Assim, a probabilidadede um objetou ser associado a uma classe qualquer em uma iteração é igual a1/m.

Em cada iteração, enquanto o objetou não tem uma classe associada, a probabilidade deleser associado a uma classei é 1

mxui. Assim a probabilidade de um objetou ser associado a uma

classei pelo algoritmo é precisamentexui.


Sabemos que para ocorrer a separação de dois objetos relacionados, eles devem ser associa-dos a alguma classe em iterações diferentes. O lema a seguir dá a probabilidade de dois objetosserem associados a classes em iterações diferentes.

Lema 3.1.2 Em uma iteração, a probabilidade de dois objetosu e v emU , relacionados pelaarestae, serem separados é2ze/m =

∑i∈L |xui − xvi|/m. A probabilidade dos dois objetosu

ev, relacionados pela arestae = u, v, serem separados pelo algoritmo é no máximo2ze.

Prova.Considerando uma classei escolhida na linha 3 do procedimentoRound_UML, a probabi-

lidade de somente um dos objetosu e v em U ser associado à classei é |xui − xvi|. Então,a probabilidade de somente um dos objetosu e v, relacionados pela arestae = u, v, serassociado a alguma classe em uma iteração é

∑

i∈L

1

m|xui − xvi| =

∑i∈L zei

m=

2ze

m.

Se os objetosu e v, relacionados pela arestae = u, v, forem associados a uma classe namesma iteração, então o custo de separaçãowe, ondee = u, v, não será pago. Isto é, em cadaiteração o algoritmo escolhe aleatoriamente uma classei ∈ L e um valorα entre 0 e 1. Sexui émaior ou igual aα entãou é associado à classei. SejaE o evento em queu e v são separadosem uma iteração eE ′ o evento em que pelo menos um deu e v é associado em uma iteração.Podemos obter uma delimitação superior da probabilidade dedois objetos relacionados seremseparados pelo processo do seguinte modo:

Pr[E ]Pr[E ′] . (3.1)

A probabilidade de ocorrer o eventoE é 2ze/m e a probabilidade de ocorrer o eventoE ′ épelo menos a probabilidade do objetou ser associado que é, pelo lema 3.1.1,1/m. Então, aprobabilidade dos objetosu ev, relacionados pela arestae = u, v, serem associados a classesdiferentes é no máximo2ze.

Com o auxílio dos lemas anteriores podemos enunciar o próximo teorema que nos dá o fatorde aproximação do algoritmo.

Teorema 3.1.3Sejax uma solução do programa linear relaxado (KTR) comcLP representandoo custo de associação ewLP representando o custo de separação da correspondente solução.O algoritmo obtém uma classificaçãox onde o custo de associação esperado écLP , e o custode separação esperado é no máximo2wLP .


Prova.Pelo lema 3.1.1, a probabilidadePr[f(u) = i] é xui. Então, a contribuição esperada deu

para a função objetivo é∑

i∈L cuixui, que é exatamente igual à contribuição deu no programalinear. Assim, o custo total de associação esperado é decLP .

A contribuição esperada da arestae = u, v para o custo de separação é exatamentewe

vezes a probabilidade dos objetosu e v serem separados, que pelo lema 3.1.2 é no máximo2ze. A contribuição esperada da arestae é no máximo2weze, que é duas vezes a contribuiçãodo programa linear. Portanto, o custo total esperado de associação sobre todos os objetos é nomáximo2wLP .

Corolário 3.1.4 Usando uma soluçãox do programa linear (KTR) obtemos uma classificaçãocom valor esperado que é no máximo duas vezes o valor de uma solução ótima.

Lema 3.1.5 O tempo de execução esperado do algoritmo Alg_UML é no máximom.

Prova.O tempo de execução esperado é dado por

∑t tPr(t), ondet é o tempo de execução e Pr(t)

é a probabilidade do tempo de execuçãot ocorrer.Pelo lema 3.1.1, a probabilidade de um objeto ser associado aqualquer classe em uma

iteração é1m

. Note que a probabilidade de um objeto ser associado a uma classe qualquer emuma iteração não é alterada pelo fato de outros objetos teremsido associados, já que os valoresdexui não são alterados durante a execução do algoritmo. Assim, a probabilidade de um objetoser associado nai-ésima iteração é dado por1/m(1− 1/m)i, e o tempo de execução esperadodo algoritmo é dado por

∞∑

i=1

i

[(1− 1

m

)i−11

m

]=

1

m

∞∑

i=1

i

(1− 1

m

)i−1

=1m(

1− 1m

)∞∑

i=1

i

(1− 1

m

)i

=1m(

1− 1m

)[ (

1− 1m

)(1−

(1− 1

m

))2

]

=1m

1− 2(1− 1

m

)+

(1− 1

m

)2

=1m1

m2

=m2

m


= m.

Assim, o tempo de execução esperado do algoritmoAlg_UMLé no máximom.

3.1.2 Árvores métricas

Antes de apresentarmos a abordagem considerada por Kleinberg e Tardos [17] para o casoda métrica geral apresentaremos os resultados obtidos por Bartal [2, 3] sobre a aproximaçãode espaços métricos através de árvores métricas. Assumimosque um espaço métricoMV =

(M, V ) é a aplicação da métricaM sobre o conjunto de pontosV .O problema de aproximação de espaços métricos depende diretamente da escolha da classe

de métricas que tomamos como sendo “simples”. Tipicamente émais fácil obter bons resultadosem problemas de otimização quando os dados respeitam algumamétrica mais “simples”. Umexemplo de métrica simples é a métrica uniforme, além da métrica uniforme vale destacar asmétricas geradas por árvores (também conhecidas como métricas aditivas).

SejaNV e MV dois espaços métricos sobre um conjunto finito de pontosV , dizemos queo espaço métricoNV dominao espaço métricoMV se para todo par de pontosu, v ∈ V ,dM(u, v) ≤ dN(u, v). SejaS um conjunto de espaços métricos “simples” sobre um conjuntodepontosV . O espaço métricoMV é dito serα-aproximado-probabilisticamente porS se existiruma distribuição de probabilidade emS, onde para cada par de vérticesu, v ∈ V a esperançada distância em um espaço métricoNV , escolhida probabilisticamente emS, é no máximoαvezes maior que a distância emMV , ou sejaE(dN(u, v)) ≤ αdM(u, v).

Se temos umaβ-aproximação para um problema de otimização, onde o espaço métrico,sobre o conjunto de dadosV , pertence à classeS, e se um espaço métricoNV /∈ S pode serα-aproximado-probabilisticamente porS então, a razão de performance dos algoritmos paraum espaço métricoNV /∈ S éαβ.

Um espaço métricoMV sobre um conjunto de pontosV pode ser visto como um grafoGM = (V, E, w), onde um pesow(e), para uma arestae ∈ E, representa a distância entreos pontos ligados pela arestae. Um exemplo de espaço métrico simples paraMV é o espaçométrico gerado pela árvore geradora de peso mínimo deGM , onde a distância entre dois ele-mentosu, v ∈ V é dada pela soma das arestas do caminho mínimo deu atév na árvore geradorade peso mínimo. Este espaço métrico possui uma distorção na distância entre os pontos de nomáximoΩ(n) [2], onden é o número de pontos emV .

Bartal [2] explora o fato de que os espaços métricos que formam a classeS e são usadospara aproximar uma métricaM , definida sobre um conjunto de pontosV , não precisam serinduzidos por um subgrafo do grafo gerado pela métricaM . Isto permite considerar uma classeonde os espaços métricos são gerados por árvores métricas e possuem outras característicasdesejáveis.


As árvores métricas que compõe uma classe de espaços métricos são chamadas de árvoresr-hierarquicamente bem separadas (r-hierarchically-well-separated treesr-HST). Temos comopropriedade das árvores métricasr-HST que o espaço métrico gerado pode ser decompostorecursivamente em subespaços métricos, e para um espaço métrico com diâmetro∆ os seussubespaços métricos terão diâmetros menores em um fator der, ou seja,∆/r, ∆/r2, ∆/r3, . . .,para umr > 1. A figura 3.4 ilustra um exemplo de uma árvorer-HST onde podemos observaras propriedades destas árvores.

Mais formalmente podemos definir uma árvorer-HST da seguinte forma.

Definição 3.1.6Uma árvore métricar-hierarquicamente bem separada (r-HST) é definidacomo uma árvore enraizada onde as arestas possuem pesos com as seguinte propriedades:

• As arestas que ligam um pai aos seus filhos tem o mesmo peso.

• Os pesos das arestas ao longo de qualquer caminho que vai da raiz até uma folha de-crescem por um fator maior que 1, que é uma potência der, ou seja, seevp e evf sãoarestas que ligam um vérticev ao seu pai ev a um de seus filhos, respectivamente, entãow(evf ) = w(evp)/r

t, para algumt >= 1.

• A distância entre dois nós da árvore é dada pela soma do tamanho das arestas do únicocaminho entre estes nós na árvore.

l ll

lr

lr2 l

r2

lr2l

r

lr

Figura 3.4: Exemplo de uma árvorer-HST.

Note que a distância entre pontos irmãos em uma árvorer-HST é uniforme. Isto permitea utilização da técnica de divisão e conquista para obter umasolução para um problema deotimização definido sobre qualquer métricaM .

O principal resultado de Bartal [2, 3] é apresentado no teorema 3.1.7

Teorema 3.1.7Todo grafo conexoG com pesos nas arestas pode serα-aproximado-probabi-listicamente por um conjunto de árvoresr-HST, que possuem um diâmetro proporcional aodiâmetro do grafoG, em tempo polinomial, ondeα = O(r log n log log n).


A construção de uma árvorer-HST que aproxima um espaço métricoMV , definida so-bre um conjunto de vérticesV , é baseada em uma partição métrica hierárquica(HierarchicalPartition Metric (HPM))do grafoGM .

Uma partição métrica hierárquica é uma partição recursiva do grafoGM , onde em cadaiteração o grafo é particionado e as arestas que definem a partição são rotuladas com um valormaior que o diâmetro do subgrafo considerado na iteração. A partição e a atribuição de rótulosé repetida para cada parte obtida. Como resultado da HPM temos uma estrutura muito próximade uma árvore HST.

A construção de uma HPM para um grafo ponderadoG = (V, E, w) é feita recursivamentecomo mostra o algoritmoAlg_HPMda figura 3.5. O algoritmoAlg_HPMutiliza como entradaum grafo com pesos nas arestas e devolve uma atribuição de rótulosℓ para as arestas.

ALGORITMO Alg_HPM(G)

ondeG = (V, E, w) é um grafo ponderado.

1. U = V

2. φ = φ(G) = |E|3. ∆ = diam(G)

4. T = φ = |E(G)|.5. SejaG o grafo obtido a partir deG contraindo as arestas eme ∈ E|w(e) < ∆

2T

6. Seja∆ = ∆/2.

7. Escolha aleatoriamente um vérticev ∈ U .

8. Escolha aleatoriamente um inteirog no intervalo[0, T ].

9. Defina o raiozg = g

T∆.

10. Defina um corteCg = u, w ∈ E(G)|d(v, u) ≤ zg < d(v, w).11. Para cadae ∈ Cg

12. ℓ(e) = ∆

13. SejaU1g = u ∈ V (G)|d(u, v) < zg eU2

g = u ∈ V (G)|d(u, v) ≥ zg.14. SejaH1

g eH2g os subgrafos induzidos deG pelos conjuntos de vérticesU1

g eU2g .

15. SeU1g 6= ∅ então

16. ExecuteAlg_HPM(H1g )

17. SeU2g 6= ∅ então

18. ExecuteAlg_HPM(H2g )

Figura 3.5: Algoritmo para a partição métrica hierárquica.

Como podemos ver na figura 3.6, o resultado da partição métrica hierárquica é uma atribuiçãode rótulosℓ para as arestas do grafoG. Os rótulos atribuídos para as arestas são representadospor tipos de linhas diferentes. Na figura 3.6(a) temos o grafoG e na figura 3.6(b) temos o resul-


(c)(a) (b) (d)

Figura 3.6: Exemplo de uma partição métrica hierárquica.

tado da primeira iteração do algoritmo. Claramente o conjunto de vérticesU2g é composto pelos

vértices do componente de maior tamanho da figura 3.6(b). Aplicando HPM para o subgrafoinduzido porU2

g temos a figura 3.6(c). Observe que as arestas rotuladas da figura 3.6(c) pos-suem o mesmo rótulo. Isto ocorre porque o diâmetro do subgrafo formado pelo conjuntoU2

g éigual ao diâmetro do grafoG. Aplicando recursivamente o algoritmoAlg_HPMpara o subgrafoformado pelo conjuntoU1

g temos a atribuição ilustrada na figura 3.6(d).Dada uma partição métrica hierárquicaℓ de um grafoG, o algoritmoAlg_HST, ilustrado

na figura 3.7, constrói uma árvorer-HST, onde cada vértice da árvorer-HST representa umsubgrafo da partição métrica deG.

Analisando as distorções geradas na criação da HPM e na construção da árvorer-HST,temos que para qualquer métricaM , definida sobre um conjuntoV de n pontos, podemosconstruir uma árvore métricar-HST, que é umaO(log n log log n)-aproximação da métricaM ,em tempo polinomial.

Recentemente Fakcheroenpholet al.[9] melhoraram o resultado de Bartal apresentando umalgoritmo que aproxima um espaço métrico qualquer por árvores métricas HST com fator deaproximaçãoO(logn).

3.1.3 Algoritmo para o caso da métrica geral (Problema ML)

Observe que, utilizando o algoritmoAlg_UML, nem sempre se obtém uma solução, com garan-tia no fator de aproximação, para instâncias do problema de classificação métrica com distân-cias variadas. Isto porque o programa linear (KTR) não considera em sua formulação o valorda função de distância.

Kleinberg e Tardos [17], utilizando o resultado obtido por Bartal [2, 3], anunciado no teo-rema 3.1.7, desenvolveram uma variação do algoritmoAlg_UML e do programa linear (KTR),que obtém soluçõesO(log m log log m)-aproximadas para instâncias do problema de classifi-cação métrica.

A idéia básica do algoritmo consiste em aproximar o espaço métrico definido pela funçãode distânciad do conjunto de classesL através de uma árvore enraizadar-HST, onder é uminteiro maior que 2, e utilizar esta aproximação do espaço métrico como um dos parâmetros deentrada para um programa linear, semelhante ao apresentadopara o problema de classificação


ALGORITMO Alg_HST(G, ℓ, r, L, k)

ondeG = (V, E, w) é um grafo ponderado,ℓ é uma partição métrica hierárquica deG,r é um fator de decréscimo da distância,L é o diâmetro do subgrafo considerado, inicialmentediam(G) ek é a raiz a quem será ligado a subárvore, inicialmente NILL.

1. Sek = NILL faça.

2. Adicione um vérticevG como sendo a raiz.

3. Apontev para o vérticevG.

4. SejaH1, . . . , Hm osm subgrafos deG gerados no primeiro nível da HPMℓ.

5. Parai = 1 atém faça

6. SeHi 6= ∅ então

7. ExecuteAlg_HST(Hi, ℓ, r, L, v)

8. Senão

9. Crie um vérticevG.

10. Conecte o vérticevG como filho dek com uma aresta de comprimentoL/2.

11. Sediam(G) < L/r então

12. Apontev para o vérticevG.

13. DecrementeL por um fator der.

14. Senão

15. Apontev para o vérticek.

16. SejaH1, . . . , Hm osm subgrafos deG gerados no primeiro nível da HPMℓ.

17. Parai = 1 atém faça

18. SeHi 6= ∅ então

19. ExecuteAlg_HST(Hi, ℓ, r, L, v)

Figura 3.7: Algoritmo para a construção de uma árvorer-HST.

uniforme.

Kleinberg e Tardos acrescentaram três novas restrições, para que uma árvorer-HST, sobre oespaço métrico das classes, possa ser utilizada pelo novo programa linear e pelo novo algoritmo.São elas:

a) O parâmetror, utilizado na construção da árvorer-HST, tem que ser maior que2.

b) Todos os nós que representam as classes devem ser folhas.

c) Os nós internos da árvore, nós que não são folhas, são apenas auxiliares.


Note que ao construir uma árvorer-HST para o espaço métrico formado pelo conjunto declassesL de uma instância do problema de classificação métrica uniforme, obtemos uma árvoreem formato de estrela, onde todas as folhas são classes. O nó central é um nó auxiliar e otamanho de todas as arestas é a metade da distância entre quaisquer duas classes, que é umvalor constante.

SejaT uma árvorer-HST, onde as classes são folhas deT , e T ′ uma subárvore qualquerdeT . Denotamos porL(T ′) o conjunto das classes que são folhas deT ′. Vamos usar a notaçãoT ′ < T para árvoresT ′ que são subárvores deT . Assim,∪T ′<T L(T ′) = L.

Após construirmos uma árvoreT , r-HST, para as classes emL, podemos formular o pro-blema como um programa linear inteiro, semelhante ao programa linear (KTG), utilizando asmesmas variáveisxui e ze utilizadas anteriormente. A principal diferença está na inclusão devariáveisxuT ′, paraT ′ < T , que é uma variável auxiliar no cálculo do custo de separaçãoeestabelecer que

xuT ′ =∑

i∈L(T ′)

xui.

Esta variável indica se a classe a qual o objetou será associado pertence à subárvoreT ′, ondeT ′ é uma subárvore enraizada em algum nó, inicialmente a raiz.

Dada uma subárvoreT ′ de T cuja raiz éy, denotamos porℓT ′ o comprimento da arestay, s, ondes é o pai dey emT . Como conseqüência da definição da variávelxui, que indicase o objetou será associado à classei, a variávelxuT ′ indica se o objetou será associado a umaclasse que pertence aL(T ′). Assim, a distância entre as classes associadas aos objetosu e v,relacionados pela arestae = u, v, é definida como

d(f(u), f(v)) =∑

T ′<T

ℓT ′ |xuT ′ − xvT ′ |.

Para auxiliar na construção do programa linear temos a variável zeT ′ que expressa o valor abso-luto |xuT ′ − xvT ′ |. A seguir apresentaremos o programa linear inteiro do problema de classifi-cação métrica usando uma árvoreT , r-HST:

min∑

e∈E

weze +∑

u∈P,i∈L

cuixui

s.t.∑

i∈L

xui = 1 ∀ u ∈ P,

ze =∑

T ′<T

ℓT ′zeT ′ ∀ e ∈ E,

zeT ′ ≥ xuT ′ − xvT ′ ∀ e = u, v ∈ E, T ′ < T,

zeT ′ ≥ xvT ′ − xuT ′ ∀ e = u, v ∈ E, T ′ < T,

xuT ′ =∑

i∈L(T ′)

xui T ′ < T,

xui ∈ 0, 1 ∀ u ∈ P, ∀ i ∈ L.

(KTTG)


Assim como no programa linear (KTG), obtemos o programa linear relaxado fazendo comque as variáveisxui recebam valores no intervalo[0, 1], ao invés dos valores binários0, 1,e acrescentamos a restriçãoxui ≥ 0 no programa linear (KTTG). Baseado nestas alteraçõesobtemos o seguinte programa linear:

min∑

e=u,v∈E

weze +∑

u∈P,i∈L

cuixui

s.t.∑

i∈L

xui = 1 ∀ u ∈ P,

ze =∑

T ′<T

ℓT ′zeT ′ ∀ e ∈ E,

zeT ′ ≥ xuT ′ − xvT ′ ∀ e = u, v ∈ E, T ′ < T,

zeT ′ ≥ xvT ′ − xuT ′ ∀ e = u, v ∈ E, T ′ < T,

xuT ′ =∑

i∈L(T ′)

xui T ′ < T,

xui ≥ 0 ∀ u ∈ P, ∀ i ∈ L.

(KTT)

No programa linear relaxado (KTT), a variávelxui pode assumir um valor fracionário entre0 e1, que o algoritmo interpreta como a probabilidade do objetou ser atribuído à classei. Peladefinição da variávelxui, a variávelxuT pode ser interpretada como a probabilidade do objetou ser associado a alguma classe pertencente ao conjunto formado pelas folhas da subárvoreT .

O algoritmoAlg_ML, apresentado na figura 3.8, utiliza como ponto de partida umasoluçãodo programa linear relaxado (KTT) e considera inicialmenteas t subárvores, que tem comoraiz um filho da raiz deT , dadas porT 1, . . . , T t (assumindo que a raiz deT possuit filhos).Em seguida são passados como parâmetros para a execução do procedimentoRound_UMLoconjunto de objetosP , um conjunto de classes, onde cada uma dast subárvores é consideradauma classe, e os valoresxuT respectivos às subárvores consideradas na iteração.

Como resultado da primeira iteração temos a associação de umconjunto de objetosP ′ ⊆ P

a cada classe representada pela subárvoreT j, ondej ∈ 1, . . . , t. Posteriormente assumimosxui = xui/xuT j , para todas as classesi ∈ L(T j) e para todou ∈ P , como uma normalizaçãodos valores dexui, para que a soma dos valores dexui em uma subárvoreT j seja igual a um epossam ser utilizados na chamada recursiva para a subárvoreT j , ondej ∈ 1, . . . , t.

Na figura 3.9 temos uma instância para o problema de classificação métrica. A figura 3.9(a)ilustra uma árvore3-HST que será utilizada pelo algoritmoAlg_ML e na figura 3.9(b) temos ografo formado pelos objetos e suas relações, já na figura 3.9(c) temos a decomposição da árvoreT em subárvores.

Os valores das arestas que ligam as subárvores deT aos seus pais são:ℓ(T1) = 3, ℓ(T2) = 3,ℓ(T3) = 1 e ℓ(T4) = 1. Os custos de atribuição estão dispostos na tabela ilustrada na figura3.10, onde o valor da célula na linhaa colunab representa o custo de associaçãocab.


ALGORITMO Alg_ML (P, L, d, c, w, T )

onde(P, L, d, c, w) é uma instância para o problema ML eT é uma árvorer-HST que aproxima a métrica deL.

1. Sejax uma solução para o programa linear (KTT)

2. ExecuteRound_ML(P, T, x)

3. Devolvaf

PROCEDIMENTO Round_ML(P, T, x)

1. yuj = xuT j ∀ 1 ≤ j ≤ t e ∀ u ∈ P , ondeT j é filho deT

2. ExecuteRound_UML(P , T 1, . . . , T t, y)

3. Paraj = 1 atét faça

4. PT j ← objetos associados à subárvoreT j

5. Se a altura deT j é igual a zero então

6. Para todou ∈ PT j faça

7. f(u) = L(T j)

8. Senão

9. Para todoi ∈ L(T j) eu ∈ P

10. xui ← xui/xuT j

11. Para todoT l < T j

12. xuT l ←∑i∈L(T l) xui

13. ExecuteRound_ML(PT j , T j ,x)

Figura 3.8: Algoritmo para o arredondamento da solução do programa linear para o casométrico.

l

i j

i j1 1T1 T4T3T2

i j

l1

3

1

3T

(a) (b) (c)y

vu1

25

G = (P, E, w)

Figura 3.9: Exemplo de uma instância para o algoritmoAlg_ML.

Para melhor ilustrar o funcionamento do algoritmoAlg_MLconsidere a instância ilustra nafigura 3.9 com os valores dex, de uma solução do programa linear (KTT), apresentados natabela da figura 3.11, onde o conteúdo de uma célulaui representa o valor dexui.

O algoritmoAlg_MLexecuta o procedimentoRound_MLpassando como parâmetros o con-juntoP , a árvoreT e a atribuição dex, representado pela tabela da figura 3.11. O procedimento


i j l

u 2 3 6v 6 5 2y 4 4 3

Figura 3.10: Custo de associação da ins-tância ilustrada na figura 3.9.

i j l T1 T2 T3 T4

u 0,6 0,2 0,2 0,8 0,2 0,6 0,2v 0,2 0 0,8 0,2 0,8 0,2 0y 0,4 0,4 0,2 0,8 0,2 0,4 0,4

Figura 3.11: Solução do programa linear(KTT) para a instância da figura 3.9.

Round_MLexecuta o procedimentoRound_UMLpassando como parâmetros o conjunto de ob-jetosP e o conjuntoT 1, . . . , Tm de classes, ondeT 1, . . . , Tm são filhos deT . Para o nossoexemplo o conjunto de classesL = T1, T2, e os valores dex passados para o procedimentosão as colunasT1 eT2 da tabela 3.11.

Supondo que a solução do procedimentoRound_UMLseja a atribuição dos objetosu e y

à subárvoreT1 e o objetov à subárvoreT2. O procedimentoRound_MLé executado recursi-vamente para a subárvoreT1 com o conjunto de objetosu, y e para a subárvoreT2 com oconjunto de objetosv. Os valores dex são atualizados para cada subárvore. Para a sub-árvoreT1 os valores dex considerados são os representados pela tabela 3.2; O procedimentoRound_MLnão é executado para a subárvoreT2 devido a esta não possuir filhos.

i j T3 T4

u 0,75 0,25 0,75 0,25y 0,5 0,5 0,5 0,5

Tabela 3.2: Os valores dex atualizados para a subárvoreT1.

Ao executarmos o procedimentoRound_MLpara a subárvoreT1 com seus respectivos ob-jetos e valores dex, este executa o procedimentoRound_UMLque devolve uma classificaçãodos objetosu e y em uma das subárvoresT3 ou T4, concluindo assim a execução do algoritmoAlg_ML.

Para analisar este algoritmo são usadas as propriedades válidas para a métrica uniforme,que foram provadas nos lemas 3.1.1 e 3.1.2, e estão adaptadas, no lema 3.1.8, para métricasaproximadas através de árvoresr-HST.

Lema 3.1.8 A probabilidade do objetou ser associado a uma subárvoreT j éxuT j . Para cadaarestae = u, v a probabilidade dos objetosu e v serem associados a classes diferentes é nomáximo

t∑

j=1

|xuT j − xvT j |.


Quando consideramos um conjunto de objetos, onde todos são associados à mesma subár-vore, temos o problema que o seu custo de separação fracionário é alterado devido à normaliza-ção aplicada sobre as variáveisxui. Como veremos, o aumento no custo de separação resultantedesta alteração é limitado no lema 3.1.10. Antes de mostrarmos este limite precisamos de al-guns fatos importantes. A prova é baseada na soma de todos os níveis da árvore e é usada apropriedade das árvoresr-HST de que o comprimento das arestas na árvore decresce exponen-cialmente conforme andamos em direção às folhas.

Lema 3.1.9 Sejax uma solução fracionária devolvida pelo programa linear (KTT) quandoaplicado a uma instância do problema ML, com o espaço métricodo conjunto de classesLaproximado através de uma árvorer-HST comr > 2, cujas folhas são classes. Então, para umobjetou e uma subárvoreT ,

∑

T ′<T

ℓT ′xuT ′ ≤ 1

r − 1ℓTxuT .

Prova.Set é a raiz deT e t′ é a raiz de uma subárvoreT ′ deT , dizemos queT ′ está no nívelj se

o caminho que parte det e chega emt′ tem exatamentej arestas e denotamos porD(T ′, T ) onível da subárvoreT ′ emT . Note que temos

∑

T ′:D(T ′,T )=j

xuT ′ ≤ xuT

para todoj ≥ 1. Assim

∑

T ′<T

ℓT ′xuT ′ =∑

j≥1

∑

T ′:D(T ′,T )=j

ℓT ′xuT ′

≤∑

j≥1

r−jℓT

∑

T ′:D(T ′,T )=j

xuT ′

≤∑

j≥1

r−jℓT xuT

≤ 1

r − 1ℓT xuT .

Lema 3.1.10Sejae = u, v uma aresta e suponha quexuT i ≤ xvT i . Se ambos,u e v, sãoassociados à subárvoreT i então o novo custo de separação fracionário é no máximo

we

xuT i

[∑

T ′<T i

ℓT ′|xuT ′ − xvT ′ |+ 1

r − 1ℓT i|xuT i − xvT i |

].


Prova.O novo custo de separação fracionário para a arestae = u, v éwe

∑T ′<T ℓT ′|xuT ′ −xvT ′ |

e seu e v são ambos associados aT i então a soma pode ser escrita como

∑

T ′<T i

ℓT ′|xuT ′ − xvT ′ | =∑

T ′<T i

ℓT ′

∣∣∣∣xuT ′

xuT i

− xvT ′

xvT i

∣∣∣∣

=∑

T ′<T i

ℓT ′

∣∣∣∣(

xuT ′

xuT i

− xvT ′

xuT i

)−

(xvT ′

xvT i

− xvT ′

xuT i

)∣∣∣∣

≤∑

T ′<T i

ℓT ′

1

xuT i

|xuT ′ − xvT ′ |+∑

T ′<T i

[1

xuT i

− 1

xvT i

]ℓT ′xvT ′ (3.2)

≤ 1

xuT i

[∑

T ′<T i

ℓT ′ |xuT ′ − xvT ′ |]

+1

r − 1ℓT ixvT i

[1

xuT i

− 1

xvT i

](3.3)

=1

xuT i

[∑

T ′<T i

ℓT ′ |xuT ′ − xvT ′ |]

+1

r − 1ℓT i

[xvT i

xuT i

− 1

]

=1

xuT i

[∑

T ′<T i

ℓT ′ |xuT ′ − xvT ′ |]

+1

r − 1ℓT i

[xvT i − xuT i

xuT i

]

=1

xuT i

[∑

T ′<T i

ℓT ′ |xuT ′ − xvT ′ |+ 1

r − 1ℓT i(xvT i − xuT i)

],

onde (3.2) é obtida usando a hipótese quexuT i ≤ xvT i e (3.3) é obtida usando o lema 3.1.9.

Teorema 3.1.11Sejax uma solução do programa linear (KTT) aplicado a uma instância doproblema ML, com o espaço métrico do conjunto de classesL aproximado através de umaárvore r-HST comr > 2, cujas folhas são classes. SejacLP e wLP o custo de associação eseparação, respectivamente, resultante da classificação fracionária x. O algoritmo Alg_MLencontra uma classificação com custo de associação esperadode cLP e custo de separaçãoesperado de no máximo

(2 +4

r − 2)wLP .

Prova.Ambas as afirmações sobre o custo da classificação são provadas por indução na profundi-

dade da árvore.Na base da indução a profundidade da árvore é 1, ou seja, a árvore T possuit filhos, que

são as classes, e os valoresxuT i = xui. Pelo teorema 3.1.3 o valor esperado para o custo deassociação écLP e o valor esperado para o custo de separação é2wLP .


SejamT 1, . . . , T t as subárvores que são filhas da raiz da árvorer-HST.Primeira afirmação: “O algoritmoAlg_ML encontra uma classificação com custo de as-

sociação esperado decLP .” Considere uma subárvoreT j no primeiro nível. Pelo lema 3.1.8,a probabilidade de um objetou ser associado a subárvoreT j é xuT j e seu for associado asubárvoreT j então a probabilidade de associação, que pelo lema 3.1.1 éxui, é normalizadapara

xui =1

xuT j

xui,

para cada classei ∈ L(T j). Por indução, uma vez que um objetou é associado a uma subárvoreT j, este é atribuído a uma classei ∈ L(T j) com probabilidadexui e assim a probabilidade doobjetou ser associado à classei em L(T j) é xuT jxui = xui. Logo, o custo de associaçãoesperado é

∑u∈P,i∈L cuixui, que é exatamentecLP .

Segunda afirmação:“O algoritmoAlg_MLencontra uma classificação com custo de sepa-ração esperado de no máximo(2+ 4

r−2)wLP .” O custo de separação fracionário para uma aresta

e = u, v é

we

∑

T ′<T

ℓT ′ |xuT ′ − xvT ′ |.

O custo de separação é computado considerando o eventoE ′ que indica se os objetosu e v sãoseparados no nível mais alto e o eventoEi que indica que os objetosu e v são associados àmesma subárvoreT i. Sejah(u, v) uma variável aleatória que indica a distância métrica entreas classes associadas aos objetosu e v. O custo de separação da arestae = u, v éweh(u, v).Então o custo de separação esperado éweE[h(u, v)] e a distância esperada entre as classesassociadas aos objetosu e v pode ser escrita da seguinte maneira

E[h(u, v)] = E[h(u, v)|E ′] · Pr[E ′] +

t∑

i=1

E[h(u, v)|Ei] · Pr[Ei].

Pelo lema 3.1.8 temos que a probabilidadePr[E ′] de que dois objetos relacionados atravésde uma aresta sejam separados no primeiro nível é no máximo

∑t

i=1 |xuT i − xvT i |. O custo deseparação neste caso é limitado pelo diâmetro da árvore que,usando propriedades das árvoresr-HST, é no máximo[2r/(r − 1)]ℓT i para qualqueri. Assim, o primeiro termo da soma dadaanteriormente é limitado por

E[h(u, v)|E ′] · Pr[E ′] ≤ 2r

r − 1

t∑

i=1

ℓT i|xuT i − xvT i |. (3.4)

Se ambos objetos forem associados à mesma subárvoreT i então, por indução no nível dasubárvore e usando o resultado da equação (3.4), o custo de separação esperado é no máximo2 + 4/(r − 2) vezes o custo de separação fracionário da solução escolhida. A probabilidade


de que ambos objetos sejam associados à mesma subárvoreT i é no máximomin(xuT i , xvT i) eusando o lema 3.1.10 podemos limitar o valor deE[h(u, v)|Ei] · Pr[Ei] da seguinte forma

E[h(u, v)|Ei] · Pr[Ei] ≤2r

r − 2

[∑

T<T i

ℓT |xuT − xvT |+1

r − 1ℓT i|xuT i − xvT i |

].

Assim o limitante final paraE[h(u, v)] fica da seguinte forma

E[h(u, v)] ≤ 2r

r − 1

t∑

i=1

ℓT i|xuT i − xvT i |

+2r

r − 2

t∑

i=1

[∑

T<T i

ℓT |xuT − xvT |+1

r − 1ℓT i |xuT i − xvT i |

]

≤ 2r

r − 2

∑

T ′<T

ℓT ′|xuT ′ − xvT ′ |.

Por definição,wLP =∑

T ′<T ℓT ′ |xuT ′ − xvT ′ | o que conclui a prova do teorema 3.1.11.

O fator de aproximação demonstrado no teorema 3.1.11 não leva em consideração o fato deque a árvorer-HST utilizada é uma aproximação do espaço métrico do conjunto de classesL.Para obter o fator de aproximação real precisamos aplicar o resultado de Bartal na aproximaçãoprobabilística de espaços métricos.

Segundo Bartal [2], para toda métricad, há um conjuntoS de árvores métricasr hierarqui-camente bem separadas (r-hierarchically-well-separated tree metrics), onde cadaT ∈ S temuma função de distânciasdT e uma distribuição de probabilidadepT , tal quedT (u, v) ≥ d(u, v)

para todoT ∈ S e todo par de objetosu, v. Além disso,dT (u, v) não é muito maior qued(u, v),mais precisamente,

∑T∈S pT dT (u, v) ≤ O(r log m log log m)d(u, v). Utilizando este resultado

Kleinberg e Tardos derivaram um algoritmoO(log m log log m)-aproximado para o problemade classificação métrica em um espaço métrico geral.

O algoritmoAlg_ML tem como parâmetro de entrada uma árvoreT que é uma árvorer-HSTcom a característica de que todas as classes são folhas. Antes de mostrar o fator de aproximaçãodeO(log m log log m) para o algoritmoAlg_ML, vamos mostrar que podemos transformar umaárvorer-HST em umar-HST onde todas as classes são folhas, com um acréscimo de um fator2 + 1/r na distância.

Lema 3.1.12 SejaT uma árvorer-HST com função de distânciadT , então existe uma árvoreT ′

r-HST com função de distânciadT ′ onde todas as classes são folhas, resultante da modificaçãoda árvoreT e para quaisquer duas classesi e j temos

dT (i, j) ≤ dT ′(i, j) ≤ (2 + 1/r)dT (i, j).


i′i

j

j i

ℓ ℓ

j′

ℓ/r

ℓ

Figura 3.12: Modificação em uma árvorer-HST para que todas as classes sejam folhas.

Prova.Para cada nó internoi da árvoreT que é uma classe, substitua este nói por um novo nói′

e coloquei como filho dei′. A maior alteração na distância ocorre se um nói possui um filhoj e ambos são classes, este caso esta ilustrado na figura 3.12. Sejaℓ = dT (i, j). Entãoi passaa ser filho dei′ e a distância entrei e i′ é igual aℓ, ej passa a ser filho de um novo nój′ e j′ éfilho de i′. Se a nova árvoreT ′ é umar-HST então a nova distânciadT ′(j, j′) ≤ ℓ/r, e temosquedT ′(i, j) = dT ′(i, i′) + dT ′(i′, j′) + dT ′(j′, j) ≤ 2ℓ + ℓ/r = (2 + 1/r)dT (i, j).

Esta modificação das árvoresr-HST é executada devido à Kleinberg e Tardos [17] conside-rarem que um nó interno de uma árvorer-HST pode ser uma classe. No entanto, se a árvorer-HST for gerada pelos algoritmos de Bartal [2, 3] ou Fakcheroenpholet al.[9] estas alteraçõesnão são necessárias, já que na árvorer-HST gerada por estes algoritmos as classes são as folhase os nós internos representam um subgrafo da partição métrica hierárquica, veja a subseção3.1.2.

A seguir, mostraremos um algoritmo que fornece um fator de aproximação esperado deO(log m log log m) para o problema ML, onde o espaço métrico é aproximado probabilistica-mente usando uma árvoreT , 3-HST, e em seguida é executado o algoritmoAlg_ML sobre estaárvore. Utilizando o algoritmo apresentado por Bartal [2] aárvoreT é escolhida com probabi-lidadepT em um conjuntoS.

ALGORITMO Alg_ML’ (P, L, d, c, w)

onde(P, L, d, c, w) é uma instância para o problema ML.

1. SejaT a árvore devolvida pelo algoritmo de Bartal

2. ExecutaAlg_ML (P, L, d, c, w, T )

Figura 3.13: Algoritmo de Kleinberg e Tardos para o problemade classificação métrica.


Teorema 3.1.13O algoritmo Alg_ML’, da figura 3.13, é um algoritmoO(log m log log m)

aproximado que consome tempo polinomial para o problema da classificação métrica, ondem é o número de classes da instância de entrada.

Prova.Sejad uma função de distância métrica sobre o conjunto das classesL. Através da apro-

ximação por árvores métricas de Bartal e do lema 3.1.12 encontramos um conjunto de árvoresmétricas 3-hierarquicamente-bem-separada que aproximad. Denotamos porS este conjuntodas árvores métricas epT , para todoT ∈ S, a distribuição de probabilidade das árvores,tal que para cada par de classesi, j ∈ L e cada árvoreT ∈ S, temos quedij ≤ dT (i, j) e∑

T∈S pT dT (i, j) ≤ O(log m log log m)dij.SejaO o custo da classificação ótimafO para a métricad. SejaOT , para uma árvoreT ∈ S,

o custo da classificaçãofO para as classes representadas pela árvoreT . Por definição da aproxi-mação através de árvores métricas temos que

∑T∈S pTOT é no máximoO(log m log log m)O.

SejaA uma variável aleatória que denota o custo resultante da utilização da métricad naclassificação devolvida pelo algoritmoAlg_ML, eAT uma variável aleatória que indica o custoresultante da utilização da métricadT na classificação devolvida pelo algoritmoAlg_ML. Peladefinição de aproximação através de árvores métricas temos queA ≤ AT , para todoT ∈ S.

Lembre-se que o custo esperado da classificação resultanteE[A] é no máximoO(log m log log m)O. SejaεT uma variável que corresponde ao evento que a árvoreT é se-lecionada no algoritmoAlg_ML’. Temos quePr(εT ) = pT e queE[AT |εT ] ≤ 6OT . O fatormultiplicativo6 é resultado da substituição do valor der por3 no teorema 3.1.11. Usando estasesperanças temos o seguinte.

E[A] =∑

T∈S E[A|εT ] · Pr[εT ]

≤ ∑T∈S pT E[AT |εT ]

≤ 6∑

T∈S pTOT

= O(log m log log m)O.

(3.5)

Note que o fator de aproximação deO(log m log log m) para o caso métrico geral ocorredevido à distorção deO(log m log log m) gerada ao aproximarmos o espaço métrico deL emuma árvore HST. Recentemente Fakcheroenpholet al. [9] apresentaram um novo limitante deO(log m) para a distorção causada ao aproximar um espaço métrico dem pontos através deárvores HST. Baseado no resultado de Fakcheroenpholet al. podemos alterar o enunciado doteorema 3.1.13 e obtemos seguinte teorema.

Teorema 3.1.14O algoritmo Alg_ML’, da figura 3.13, é um algoritmoO(log m) aproximadoque consome tempo polinomial para o problema da classificação métrica, ondem é o númerode classes.

3.2. Programação Linear com Interpretação de Fluxo em Rede 35

3.2 Programação Linear com Interpretação de Fluxo em Rede

Chekuriet al. [7], motivados pelo fato de que para utilizar a formulação apresentada por Klein-berg e Tardos [17], é preciso uma aproximação do espaço métrico, desenvolveram uma novaformulação, que pode ser aplicada diretamente às instâncias do caso uniforme e do caso métrico.

Para definir o novo programa linear, Chekuriet al. [7] usaram duas variáveis:

• xui, como na formulação de Kleinberg e Tardos [17], é uma variável que indica que oobjetou está associado à classei, para cada objetou ∈ P e cada classei ∈ L,

• xuivj indica que o objetou está associado à classei e o objetov está associado à classej,ou seja, que os objetosu ev são associados a classes diferentes.

Nesta nova formulação é mantida a restrição de que cada objeto deve ser associado a exata-mente uma classe, o que é representado pela restrição

∑

i∈L

xui = 1.

Além disso, é acrescentada a restrição

m∑

j=1

xuivj − xui = 0

que força consistência nas variáveisxuivj . Observe quexuivj será1 somente sexui = 1 exvj = 1. Já a restriçãoxuivj − xvjui = 0 expressa a simetria entre estas variáveis. Nestaformulação usaremos a notaçãoN(u) para especificar o conjunto de objetos que têm relaçãocom o objetou no grafoG = (P, E). A formulação relaxada é apresentada a seguir.

min∑

u∈P

∑

i∈L

cui · xui +∑

e=u,v∈E

∑

i∈L

∑

j∈L

we · dij · xuivj

s.a.∑

i∈L xui = 1 ∀ u ∈ P,∑j∈L xuivj − xui = 0 ∀ u ∈ P, ∀ v ∈ N(u), ∀ i ∈ L,

xuivj − xvjui = 0 ∀ e = u, v ∈ E, ∀ i, j ∈ L,

xui ≥ 0 ∀ u ∈ P, ∀ i ∈ L,

xuivj ≥ 0 ∀ e = u, v ∈ E, ∀ i, j ∈ L.

(CKNZ)

Para auxiliar na compreensão e na análise desta formulação,Chekuriet al. [7] constroemuma rede de fluxo, levando em conta que o conjunto de classesL = 1, . . . , m é representadopor uma seqüência de inteiros. A rede de fluxos, ilustrada na figura 3.14, é construída da formacomo segue.


...

...u1 u2 u3 um

vmv3v2v1

xu1 xu2 xu3 xum

xv2 xv3xv1 xvm

Figura 3.14: Rede de fluxosH(u, v) para uma arestau, v ∈ E.

Para cada arestau, v ∈ E é associado um grafo completo bipartidoH(u, v) com os vér-ticesu1, . . . , um e v1, . . . , vm, estes vértices representam todas as possíveis classificaçõesdeu e v. Para cada par de vérticesui, vj, com1 ≤ i, j ≤ m, há uma arestaui, vj no grafoH(u, v). Durante esta seção vamos nos referir às arestasui, vj por links.

Supondo que os valores das variáveisxui, para todou ∈ P e i ∈ L, foram determinados,usando estes valores o grafoH(u, v) é interpretado como uma rede de fluxo da seguinte forma:

• a alimentação dos vérticesui éxui, ∀ 1 ≤ i ≤ m.

• a demanda dos vérticesvj éxvj , ∀ 1 ≤ j ≤ m.

• o custo de transportar uma unidade de fluxo deui paravj édij , ∀ 1 ≤ i, j ≤ m.

Sejax uma solução do programa linear (CKNZ) e sejae = u, v ∈ E uma aresta. Como asvariáveisxui exvi são a produção e a demanda na rede de fluxosH(u, v), podemos interpretaro valor atribuído à variávelxuivj como a quantidade de fluxo que passa pelolink ui, vj emH(u, v). A contribuição da arestae para o custo de separação é o valor do transporte ótimo dofluxo entreu1, . . . , um ev1, . . . , vm.

No restante desta seção, vamos denotar pordLP (u, v) a distância entre as classes associadasaos objetosu ev em uma solução ótima (fracionária) do programa linear (CKNZ). Esta distânciaé o custo do transporte ótimo emH(u, v), que é

∑i,j∈L dijxuivj .

Os custos do transporte ótimo nas redesH(u, v), para todou, v ∈ P , induz uma métricano grafoG = (P, E), já que, para qualqueru, v, y ∈ P , o custo do transporte deu parav nãopode ser maior que a soma dos custos dos transportes deu paray e dey parav. Esta métricaé estudada na literatura de processamento de imagens com o nome deearth mover’s metric[20, 21].

Esta rede de fluxo não é implementada realmente, devido ao seualto custo. Ela serve apenaspara auxiliar na compreensão e análise dos algoritmos.


Chekuriet al. [7] analisam a utilização do programa linear (CKNZ) para os problemas declassificação métrica uniforme, classificação métrica linear e classificação métrica truncada.

3.2.1 O caso da métrica uniforme

Kleinberg e Tardos com sua formulação (KTR) obtiveram uma 2-aproximação para este casousando o algoritmo de arredondamentoAlg_UML. Aplicando este algoritmo na solução fra-cionária do programa linear (CKNZ), Chekuriet al. obtiveram o mesmo fator de aproximaçãopara o problema de classificação uniforme.

Para obter tal fator de aproximação, estes autores mostraram que, usando o resultado daformulação (CKNZ) no algoritmoAlg_UML apresentado por Kleinberg e Tardos [17], o valorda solução devolvida é menor ou igual ao valor da solução do algoritmoAlg_UML, que utilizao resultado da formulação (KTR). Em outras palavras, a formulação (CKNZ) é semelhante aformulação (KTR) para o problema de classificação métrica uniforme.

Teorema 3.2.1O fator de aproximação do algoritmo Alg_UML não é maior que 2 quandousamos a formulação (CKNZ) no lugar da formulação (KTR).

Prova.

Sabemos que utilizando a formulação (KTR) o algoritmoAlg_UML tem um fator de aproxi-mação igual a 2, para que este fator não se altere é necessáriomostrar que o valor devolvido pelaformulação (CKNZ) não é maior que o valor obtido da formulação (KTR), quando aplicado auma instância do problema de classificação métrica uniforme. A função objetivo da formulação(KTR) é

∑

u∈P

∑

i∈L

cuixui +1

2

∑

e=u,v∈E

m∑

i=1

we|xui − xvi|

enquanto que a função objetivo da formulação (CKNZ) é

∑

u∈P

∑

i∈L

cuixui +∑

e=u,v∈E

m∑

i=1

m∑

j=i

wedijxuivj .

Note que o custo de atribuição, em ambas as formulações, é definido pelas variáveisxui etêm as mesmas contribuições para a função objetivo. Já a expressão que representa o custo deseparação, que no programa linear (KTR) é dado por

1

2

∑

e=u,v∈E

m∑

i=1

we|xui − xvi|


e no novo programa linear (CKNZ) é dado por

∑

e=u,v∈E

m∑

i=1

m∑

j=i

wedijxuivj ,

são diferentes. Para que seja verdadeira a afirmação de que o fator de aproximação do algoritmoAlg_UMLnão é maior que 2, quando a formulação (CKNZ) é usada, é preciso mostrar que

∑

e=u,v∈E

m∑

i=1

m∑

j=i

wedijxuivj ≤1

2

∑

e=u,v∈E

m∑

i=1

we|xui − xvi|.

Como estamos analisando a desigualdade apenas para o caso dedistâncias métricas uni-formes, o valor assumido pela função de distância, utilizado no lado esquerdo da desigualdade,será0 ou 1, sendo0 somente quandoi = j. Assim, se considerarmos apenasi 6= j podemoseliminar a função de distância, e também, podemos dividir a desigualdade porwe, eliminandoo pesowe. Fazendo estas alterações, temos:

∑

e=u,v∈E

m∑

i=1

m∑

j=1,j 6=i

xuivj ≤1

2

∑

e=u,v∈E

m∑

i=1

|xui − xvi|. (3.6)

Esta desigualdade considera todas as arestas entre objetose todas as classes. Vamos provarque para cada aresta do somatório acima a desigualdade é válida. Assim basta provar a seguintedesigualdade para cada arestae = u, v ∈ E.

m∑

i=1

m∑

j=1,j 6=i

xuivj ≤1

2

m∑

i=1

|xui − xvi|. (3.7)

Claramente se a desigualdade (3.7) for válida então a desigualdade (3.6) também é válida.Ao considerarmos uma arestae = u, v temos duas possibilidades. A primeira em que os

objetosu e v possuem probabilidades de associação iguais, ou sejaxui = xvi, para todoi ∈ L,fazendo com que1

2

∑m

i=1 |xui − xvi| = 0.Neste caso, na formulação (CKNZ), pelas restrições

m∑

j=1

xuivj = xui ∀ u ∈ P, ∀ v ∈ N(u), ∀ i ∈ L

exuivj − xvjui = 0 ∀ e = u, v ∈ E, ∀ i, j ∈ L, as variáveisxuivj , parai 6= j, são forçadas aassumir valor zero, enquanto que as variáveisxuivi tendem a assumir valores diferentes de zero.

Para melhor ilustrar esta atribuição de valores para as variáveisxuivj , considere a rede defluxos H(u, v). O custo de transportar uma unidade de fluxo do vérticeui para o vérticevj


é igual ad(i, j) e a produçãoxui do vérticeui é igual a demandaxvi do vérticevi, para todo1 ≤ i ≤ m. Baseado nisso, o transporte ótimo do fluxo entre os vérticesui e vi é feito atravésdas arestasui, vi. Estas arestas são escolhidas devido ao custo de transportar uma unidade defluxo através delas ser igual ad(i, i) = 0. Podemos interpretar o valor da variávelxuivj como aquantidade de fluxo que passa pela arestaui, vj. Assim, devido à probabilidade de associaçãodos objetosu e v serem iguais, as variáveisxuivj que assumem valores diferentes de zero sãoaquelas em quei = j. Como estas variáveis não são consideradas no somatório, temos que∑m

i=1

∑m

j=1,j 6=i xuivj = 0.

A segunda possibilidade é de que os objetosu e v possuem probabilidades de associaçãodiferentes, fazendo com que1

2

∑m

i=1 |xui − xvi| > 0. Neste caso, na rede de fluxosH(u, v), otransporte do fluxo que é considerado para um vérticeui é apenas aquele que não é consumido,ou produzido porvi, ou seja,|xui−xvi|. Assim o fluxo total na redeH(u, v), que é representadopor

∑m

i=1

∑m

j=1 xuivj , é igual a∑m

i=1 max0, xui − xvi. Esta somatória representa o fluxoenviado do conjunto de vérticesui para o conjunto de vérticesvi e que pela restrição

∑m

i=1 xui =

1 do programa linear (CKNZ) é igual ao fluxo no sentido contrário. Assim podemos reescreveresta somatória como1

2

∑m

i=1 |xui−xvi|, ou seja, ela é igual à contribuição da formulação (KTR).

3.2.2 O caso da métrica linear

Para o problema de classificação métrica linear (LML) Chekuri et al. [7] apresentam um algo-ritmo que, utilizando uma solução fracionária do programa linear (CKNZ), obtém uma soluçãocom valor esperado igual à solução fracionária do programa linear (CKNZ). No problema declassificação métrica linear temos as mesmas características de um problema de classificaçãométrica, com a diferença que para cada classe é atribuído um número inteiro positivo nãorepetido e a função de distância entre as classes é dada pelo módulo da diferença entre elas;i.e.,d : L× L→ N+, dij = |i− j|.

O Algoritmo para o Problema LML

O algoritmo para o problema de classificação métrica linear,apresentado na figura 3.15, temcomo ponto de partida a resolução do programa linear (CKNZ),em seguida é escolhido umvalor aleatórioθ entre 0 e 1, que é utilizado no arredondamento da solução fracionária doprograma linear (CKNZ).

Para entender melhor o procedimento de arredondamento, veja a figura 3.16. Nesta figuratemos os valoresα de um objetou em relação a todas as classes do conjuntoL = 1, 2, 3, 4.Observe que o objetou tem maior probabilidade de ser associado à classe3, devido ao in-tervalo entreα(u, 2) e α(u, 3) ser o maior intervalo em[0, 1], e o tamanho deste intervalo é


ALGORITMO ALG_LML (P, L, d, c, w)

onde(P, L, d, c, w) é uma instância para o problema LML.

1. Sejax uma solução para o programa linear (CKNZ)

2. θ ← random[0, 1]

3. Para todou ∈ P

4. Parai = 1 atém

5. α(u, i)←∑i

j=1 xuj

6. Para todou ∈ V

7. Sejai tal queα(u, i− 1) < θ ≤ α(u, i)

8. f(u)← i

9. Devolvaf

Figura 3.15: Algoritmo para o arredondamento do resultado do programa linear (CKNZ).

xu3. A garantia de que todos os objetos serão associados a algumaclasse é dada pela restrição∑m

i=1 xui = 1.

α(u,1) α(u,2) α(u,3) α(u,4)

Figura 3.16: Exemplo de valores paraα.

O valor esperado da solução inteira devolvida pelo algoritmo Alg_LML, para o problemade classificação métrica linear, é igual ao valor da solução fracionária devolvido pelo programalinear (CKNZ). Para mostrar que isso é verdade temos que analisar a esperança do custo deassociação e separação. Para cada objetou ∈ P definimos uma variável aleatóriaL(u), ondeL(u) representa a classe a quem o objetou é associado no algoritmoAlg_LML, e a probabilidadede L(u) = i é xui. Isto significa que o custo de associação esperado para um objeto u é∑m

i=1 xuicui que é exatamente o custo de associação no programa linear (CKNZ).

Lema 3.2.2 O valor esperado da distância entre as classes associadas aos objetosu e v, parauma arestau, v ∈ E, é

E[d(L(u), L(v))] =

m∑

i=1

|α(u, i)− α(v, i)|.

Prova.Para auxiliar na análise, definimos as variáveis bináriasZ1, . . . , Zm−1 cujos valores são


definidos da seguinte forma:

Zi =

1 se minL(u), L(v) ≤ i < maxL(u), L(v)0 caso contrário.

Em outras palavrasZi é 1 sei estiver no intervalo entreL(u) eL(v). Então, comodij = |i− j|,fica claro que

d(L(u), L(v)) =m−1∑

i=1

Zi.

Conseqüentemente,E[d(L(u), L(v))] =∑m−1

i=1 E[Zi]. Afirmamos que

E[Zi] = Pr[Zi = 1] = |α(u, i)− α(v, i)|. (3.8)

O lema é facilmente provado usando a igualdade 3.8. Para provar a igualdade 3.8 suponha, semperda de generalidade, queα(u, i) ≥ α(v, i). Seθ < α(v, i) entãoL(u) eL(v) são menores ouiguais ai. Seθ > α(u, i) entãoL(u) eL(v) são maiores quei. Em ambos os casosZi = 0. Seθ ∈ [α(v, i), α(u, i)] entãoL(u) ≤ i e L(v) > i, o que implica queZi = 1. Assim,Pr[Zi = 1]

é exatamente|α(u, i)− α(v, i)|.

De posse da esperança da distância entre as classes atribuídas aos extremos de uma arestae = u, v, podemos estimar qual é a contribuição desta aresta para a função objetivo. Comoindicado na seção 3.2, a contribuição da arestae = u, v ∈ E para a função objetivo é igualao custo do transporte ótimo do fluxo no grafo completo bipartido H(u, v). Vale lembrar queo valor da distância entre as classes associadas aos objetosu, v no programa linear (CKNZ) édLP (u, v) =

∑i,j dij · xuivj .

Lema 3.2.3 A seguinte desigualdade é válida para a métrica linear

dLP (u, v) ≥m∑

i=1

|α(u, i)− α(v, i)|.

Prova.Analisando a estrutura da redeH(u, v) podemos observar que: Se a produção deui, que

é igual axui, for igual ao consumo devi, que é igual axvi, para todoi, significa que os doisobjetosu e v serão associados à mesma classei. Devido ao custo de transportar uma unidadede fluxo deui paravj ser igual adij, quandoxui é igual axvi, para todoi, o custo de transportaro fluxo na redeH(u, v) é zero, ou seja, o custo de separação é zero.

No caso em que a produçãoxui é maior que o consumoxvi temos um fluxo excedente emrelação à classei, neste caso dexui − xvi. Este fluxo excedente será consumido por um outronó e para tanto precisa ser “transportado” através da redeH(u, v). Vale lembrar que o custo


de transportar uma unidade de fluxo deui paravj é igual adij . Sexvi for maior quexui, aquantidade de fluxo excedente éxvi − xui. Assim, o fluxo excedente na rede de fluxosH(u, v)

em relação a uma classei é |xui − xvi|.O que é consumido no intervalo1, 2, . . . , i é minα(u, i), α(v, i) e por conseqüência

|α(u, i)−α(v, i)| é a quantidade de fluxo excedente, que será enviada para fora deste intervalo,o que significa que será cobrada para que esta quantia excedente de fluxo seja transportada.

Aplicando este argumento a todos os valores dei, obtemos que o custo de transporte ótimodo fluxo emH(u, v) é precisamente

∑m

i=1 |α(u, i)− α(v, i)|.

Assim obtemos que o custo esperado da arestae = u, v ∈ E, após o arredondamento,não é maior que sua contribuição para a função objetivo do programa linear, ou seja, ogapdeintegralidade do programa linear (CKNZ) para o caso da métrica linear é um.

3.2.3 Melhora no fator de aproximação para o caso de distâncias métricaslineares truncadas (TML)

No capítulo 4 é apresentado uma abordagem para o problema de classificação métrica desen-volvida por Gupta e Tardos [11], que utiliza algoritmos de fluxo em redes para obter umasolução para uma instância do problema de classificação métrica truncada. O problema declassificação métrica truncada é uma variação do problema declassificação métrica onde asclasses são definidas como inteiros de1 atém e a distância entre duas classesi e j é dada pelafunção de distânciadij = min(|i− j|, M), ondeM é o valor máximo da distância.

Gupta e Tardos, utilizando algoritmos de fluxo em redes, obtiveram um algoritmo polino-mial que obtém uma solução de valor no máximo4 vezes o valor ótimo para o problema TML.Com o programa linear (CKNZ) Chekuriet al. [7] obtiveram uma(2 +

√2)-aproximação,

melhorando o resultado prévio de Gupta e Tardos [11].A métrica truncada do conjunto de classesL pode ser vista como um grafo formado por um

caminho contendom vértices, que representam asm classes, e para cada par de vérticesi, j,ondedij > M , é acrescentada uma aresta de tamanhoM , assim como ilustrado na figura 3.17.Podemos considerar este grafo como um caminho com o truncamento emM implícito. Istopermite utilizar, com modificações apropriadas, a idéia utilizada para o caso das distânciasmétricas lineares.

Ao contrário do algoritmo apresentado por Gupta e Tardos [11] para o caso das distânciasmétricas truncadas, o algoritmo apresentado por Chekuriet al. [7] utiliza uma solução do pro-grama linear. O algoritmoAlg_TML_CKNZ, apresentado na figura 3.18, tem como parâmetrosde entrada o conjunto de objetosP , o conjunto de classesL e um valorM ′ que é maior ou igualaM e é definido na análise do algoritmo.

O algoritmoAlg_TML_CKNZgeneraliza o algoritmo de arredondamento para o problema


1 11 1 1

11 1

MM

MM

M

M

Figura 3.17: Grafo para a métrica truncada comM = 5.

ALGORITMO Alg_TML_CKNZ(P, L, d, c, w, M ′)

onde(P, L, d, c, w) é uma instância para o problema TML.

1. Sejax uma solução para o programa linear (CKNZ)

2. Enquanto existir objeto não classificado

3. Escolha aleatoriamente um inteiroℓ em[−M ′ + 2, m] com probabilidade uniforme

4. SejaIℓ o intervalo[ℓ, ℓ + M ′ − 1]

5. θ ← random[0, 1]

6. Para todou ∈ P não está classificado

7. Para todoi ∈ Iℓ

8. Se∑i−1

j=ℓ xuj < θ ≤∑i

j=ℓ xuj

9. f(u)← i

10. Devolvaf

Figura 3.18: Algoritmo para o caso das distâncias truncadasutilizando a formulação (CKNZ).

UML e LML de uma forma natural. Uma vez queℓ é selecionado e o intervaloIℓ é definido, oarredondamento é similar ao da métrica linear. A principal diferença entre o algoritmoAlg_LMLe o algoritmoAlg_TML_CKNZé que no primeiro um objeto sempre é associado a uma classeem uma iteração. Já no algoritmoAlg_TML_CKNZum objeto pode não ser associado em umaiteração, devido a cada iteração considerar apenas parte doconjunto de classes. Se dois objetossão classificados em iterações separadas assumimos que a distância entre estas classes éM .

A melhora no fator de aproximação é obtida através de uma análise cuidadosa do algoritmo.A análise guia para a escolha de umM ′ que resulta na melhor garantia de aproximação, ondeM ′ ≥M .

Lema 3.2.4 Em uma iteração qualquer, a probabilidade de um objetou, não classificado, serassociado à classei naquela iteração é exatamente

xui ·M ′/(m + M ′ − 1).

A probabilidade deu ser associado a alguma classe éM ′/(m + M ′ − 1). Assim

Pr[L(u) = i] = xui.


Prova.Seℓ é escolhido no primeiro passo de uma iteração e sei ∈ Iℓ, então a probabilidade de

associar o objetou à classei é exatamentexui e, sei 6∈ Iℓ, a probabilidade é zero. O número deintervalos que contêmi éM ′, devido ao fato de podermos escolherℓ para delimitar o intervaloque contemi deM ′ formas diferentes. Assim, a probabilidade do objetou ser associado a umaclassei em uma iteração é a probabilidade de associar o objetou a classei vezes a probabilidadede se escolher a classei que resulta emxui ·M ′/(m + M ′ − 1).

Segue deste lema que, com alta probabilidade, todos os objetos são associados emO(m log n)

iterações. O próximo lema delimita o valor esperado da distância entreL(u) eL(v) em funçãodeM , relembrando quedLP =

∑e=u,v∈E

∑i∈L

∑j∈L dij · xuivj .

Lema 3.2.5 A distância esperada entreL(u) e L(v) satisfaz a seguinte desigualdadeE[d(L(u), L(v))] ≤ (2 + max2M

M ′ ,M ′

M)dLP (u, v).

O lema 3.2.5 será provado mais adiante devido à necessidade de outros resultados anteriores.

Teorema 3.2.6Há um algoritmo(2+√

2)-aproximado para o problema de classificação métricaquando as distâncias são métricas lineares truncadas.

Prova.Note que o algoritmo e a análise são facilmente generalizados para o caso em queM ′ é

um número real. Observando a desigualdade do lema 3.2.5, o valor de M ′ que minimiza afunçãomax2M

M ′ ,M ′

M é√

2M . Assim, pelos lemas 3.2.4 e 3.2.5, seM ′ =√

2M temos umalgoritmo(2 +

√2)-aproximado para o problema de classificação métrica quandoas distâncias

são métricas lineares truncadas.

Com o objetivo de provar o lema 3.2.5 vamos analisar o efeito do procedimento de arredonda-mento na distância esperada entre as classes associadas aosobjetos de uma arestae = u, v ∈E. Consideraremos uma iteração ondeu e/ouv serão associados a uma classe. Podem acontecerdois casos:

• Somente um dos objetos é associado em uma iteração, ou seja, são separados, e pagare-mos a distânciaM .

• Os dois objetos são associados na mesma iteração e pagaremosa distância entre as classesque estão no mesmo intervalo.

O interesse principal aqui é na distância esperada entre as classes associadas au ev em umaiteração. Vamos utilizar o grafoH(u, v), definido no início da seção 3.2, para nos auxiliar naprova do lema 3.2.5. Denotaremos as arestasui, vj do grafoH(u, v) por links.


Dado um intervaloIℓ = [ℓ, ℓ + M ′ − 1], podemos dividir oslinks interessantes deH em 3categorias. Consideramoslinks interessantes aqueles que têm pelo menos um dos extremos nointervaloIℓ. As 3 categorias delinks interessantes estão ilustradas na figura 3.19 e são divididasda seguinte forma:

• Linksde cruzamento à esquerda, que ligam um vérticeui, comi ∈ Iℓ, a um vérticevj , talquej < ℓ e ℓ é o limite à esquerda do intervaloIℓ = [ℓ, ℓ + M ′ − 1]. O conjunto de taislinks é denotado porLCRS(Iℓ). Observe que olink de cruzamento à esquerda tambémpode seruj, vi, ou seja, o vérticeuj é quem está à esquerda do intervaloIℓ.

• Links internos são oslinksque ligamui avj , ondei, j ∈ Iℓ e formam o conjuntoINT(Iℓ).

• Links de cruzamento à direita são aqueles que ligam um vérticeui, com i ∈ Iℓ, a umvérticevj, tal quej > ℓ + M ′ − 1, ondeℓ + M ′ − 1 é o limite à direita do intervaloIℓ = [ℓ, ℓ + M ′ − 1]. Tais links formam o conjuntoRCRS(Iℓ). Observe que olink decruzamento a direita também pode seruj, vi, ou seja, o vérticeuj é quem está à direitado intervaloIℓ.

• Denotamos porCRS(Iℓ) a união deLCRS(Iℓ) comRCRS(Iℓ).

I1

links cruzamento esquerda

links internos links cruzamento direita

Figura 3.19:Links interessantes para o intervaloIℓ

Usaremos a seguinte notação no resto da prova.

• e = ui, vj é umlink (aresta) emH(u, v) que liga os vérticesui evj .

• de = dij é a distância truncada entre as classesi e j.

• |e| = |i− j| é a distância linear entre as classesi e j.


• xe representa o valor dexuivj , que é interpretado como a quantidade de fluxo que passado vérticeui para o vérticevj .

• Sejae ∈ CRS(Iℓ) e sejai ∈ Iℓ a classe a quale está ligada. Denotamos poreℓ a quantidade(ℓ + M ′ − 1− i), que é a distância dei até o limite direito do intervaloIℓ.

• x(u, Iℓ) =∑

i∈Iℓxui é o fluxo deu associado pelo programa linear (CKNZ) ao intervalo

Iℓ.

Lema 3.2.7 A probabilidade deu e v serem separados em uma iteração, ou seja, apenas umdos objetosu e v é associado a uma classe pertencente ao intervaloIℓ, dado queℓ é escolhidono primeiro passo da iteração, é no máximo

∑

e∈CRS(Iℓ)

xe.

Prova.Olhando pela perspectiva de fluxo na redeH(u, v), a quantidade de fluxo que é produzida

no intervaloIℓ e não é consumida pelos vértices internos ao intervaloIℓ é dada por|x(u, Iℓ)−x(v, Iℓ)|, que é exatamente a probabilidade de separação dos objetosu e v. Esta quantidadeexcedente de fluxo é transportada para fora do intervaloIℓ através doslinks de cruzamento àesquerda e à direita. Assim

|x(u, Iℓ)− x(v, Iℓ)| ≤∑

e∈CRS(Iℓ)

xe. (3.9)

Lema 3.2.8 Para dois vérticesu ev não classificados antes de uma iteração, sejapℓ a distânciaesperada entre as classes associadas a estes objetos, condicionado ao evento queℓ é escolhidono primeiro passo da iteração e ambos foram associados a classes pertencentes ao intervaloIℓ. Então:

pℓ ≤∑

e∈CRS(Iℓ)

eℓxe +∑

e∈INT (Iℓ)

|e|xe.

Algumas intuições antes da prova. Uma vez queℓ é escolhido, o arredondamento é exata-mente o mesmo que para o caso de métricas lineares, restrito ao intervaloIℓ. Vimos no lema3.2.2 o valor exato do custo esperado para o processo de arredondamento. No entanto não temosum lema equivalente ao lema 3.2.3 que delimita a distância utilizada pelo programa linear, de-vido aIℓ ser apenas um subintervalo do caminho formado pelas classesde1, . . . , m, e ter seutamanho truncado.


A principal dificuldade é em relação aoslinks que pertencem ao conjuntoCRS(Iℓ). Esteslinks são “carregados” de um valoreℓ (diferente dede, que é o valor pago pelo programa li-near) para que possamos pagar o custo do transporte ótimo do fluxo induzido pelos valoresfracionários das variáveisxui exvi.Prova.

Fixe ℓ e, sem perda de generalidade, suponha quex(u, Iℓ) ≥ x(v, Iℓ). Com probabilidadeq = x(v, Iℓ) ambos,u e v são associados a classes emIℓ. Analisando a distância esperadabaseada no evento em que ambas as classes associadas aos objetosu ev pertencem ao intervaloIℓ, uma vez que o intervaloIℓ é fixado, o arredondamento é muito similar ao caso das métricaslineares.

Seja

α(u, i) =ℓ+i∑

j=ℓ

xuj ,

para0 ≤ i ≤ M ′, o fluxo acumulado deu nas primeirasi + 1 classes do intervaloIℓ. Nocaso em queu e v são associados a classes no intervaloIℓ assumimos que a distância é li-near e ignoramos o truncamento. Pelo Lema 3.2.3 a distância esperada entreu e v é igual a∑M ′−1

i=0 |minq, α(u, i)−α(v, i)| que limitamos superiormente por∑M ′−1

i=0 |α(u, i)−α(v, i)|.Observe que a contribuição deα(u, i) para a distância, quandoα(u, i) é maior queq, é descon-siderada por ser a quantidade de fluxo que não é consumida pelos vértices internos ao intervaloIℓ na redeH(u, v). Baseado nesse limitante podemos substituirpℓ por

∑M ′−1i=0 |α(u, i)−α(v, i)|.

A seguinte desigualdade é válida

M ′−1∑

i=0

|α(u, i)− α(v, i)| ≤∑

e∈CRS(Iℓ)

eℓxe +∑

e∈INT(Iℓ)

|e|xe. (3.10)

Para provar que a equação (3.10) é verdadeira, consideramoscadalink e = (ua, vb) ∈CRS(Iℓ)

⋃INT(Iℓ) e somamos sua contribuição para o termoqi = |α(u, i) − α(v, i)|, com

0 ≤ i < M ′. Sejae = ua, vb ∈ INT(Iℓ). É claro quee contribui exatamente comxe paraqi

sea ≤ i e b > i ou a > i e b ≤ i. Caso contrário sua contribuição é 0. Assim, a contribuiçãototal dee para

∑qi éxe|a− b| = xe|e|.

Para melhor compreender a contribuição dolink e = ua, vb ∈ INT(Iℓ) para∑

qi, observea figura 3.20. A região sombreada da figura representa o fluxo computado paraqi. Alémdisso, podemos considerar olink e = ua, vb como umlink de cruzamento da regiãoqi, oque significa que é uma quantidade de fluxoxe excedente da regiãoqi, e como o custo de setransportar uma unidade de fluxo pelolink e = ua, vb é igual ad(a, v) = |a− b| temos que acontribuição total dee para

∑qi éxe|a− b| = xe|e| .

Agora, suponha quee = ua, vb ∈ LCRS(Iℓ) e, sem perda de generalidade, quea ≥ ℓ

e b < ℓ. O caso em quea < ℓ e b ≥ ℓ é análogo. Olink e contribui comxe paraα(u, i),


vbvi

uiua

ℓ ℓ + M ′ − 1Iℓ

Figura 3.20: Contribuição dolink ua, vb ∈ INT(Iℓ) paraqi = |α(u, i)− α(v, i)|.

coma − ℓ ≤ i < M ′, e contribui com 0 paraα(v, i), com0 ≤ i < M ′, já queb está fora dointervaloIℓ. Assim, a contribuição dee paraqi é xe, sea − ℓ ≤ i < M ′, e 0 caso contrario. Acontribuição total dee para

∑qi éxe|ℓ + M ′ − 1− a| = eℓxe. Um argumento similar é valido

quandoe ∈ RCRS(Iℓ).

uj ua

vb vj vi

ui

Iℓℓ ℓ + M ′ − 1

Figura 3.21: Contribuição dolink ua, vb ∈ CRS(Iℓ) paraqi = |α(u, i)− α(v, i)|.

Para melhor compreender a contribuição dolink e = ua, vb ∈ LCRS(Iℓ) para∑

qi, ob-serve a figura 3.21. Nesta figura, até o momento em quei = 1, que considera o fluxo até osvérticesuj e vj , a contribuição dolink ua, vb para a quantidadeqi é nula. O valorxe passaráa contribuir paraqi no momento em quei = a − ℓ, que é o momento que a quantidadexua,produzida pelo vérticeua, é computada paraα(u, i), e essa contribuição é mantida para todosos valores dei maiores quea − ℓ, até o fim do intervaloIℓ. Comovb, o outro extremo dolinkua, vb, está fora do intervaloIℓ, a quantidadexvb não influenciará no valor deα(v, i) e porconseqüência não influencia no valor deqi fazendo com que a contribuição total dee para

∑qi

éxe|ℓ + M ′ − 1− a| = eℓxe. A mesma argumentação é válida parae ∈ RCRS(Iℓ).

Prova do lema 3.2.5Prova.

Dada uma iteração ondeu e v são dois objetos não classificados, denotamos porPr[u ∧ v]


a probabilidade de ambos serem associados,Pr[u ⊕ v] a probabilidade de exatamente um serassociado ePr[u∨v] a probabilidade de pelo menos um ser associado. Vamos definirum limitesuperior paraE[d(L(u), L(v))] da seguinte forma: Seu e v são separados em alguma iteraçãoentão, podemos simplificar o limite superior da distância por M . Usando esta simplificação, aseguinte desigualdade é válida.

E[d(L(u), L(v)] ≤ Pr[u⊕ v] ·M + Pr[u ∧ v] · E[d(L(u), L(v))|u ∧ v]

Pr[u ∨ v]. (3.11)

Definimos um limite superior para os componentes da parte direita da desigualdade comosegue:

• Limitamos inferiormentePr[u ∨ v] por Pr[u] que, pelo lema 3.2.4, é igual aM ′/(m +

M ′ − 1).

• Limitamos superiormentePr[u ⊕ v] por 1(m+M ′−1)

∑ℓ

∑e∈CRS(Iℓ)

xe, que é a probabili-dade de escolher um intervaloIℓ vezes a probabilidade de separar os objetosu e v que,pelo lema 3.2.7, é

∑ℓ

∑e∈CRS(Iℓ)

xe.

• Pela definição depℓ, no lema 3.2.8, temos o seguinte:

Pr[u ∧ v]E[d(f(u), f(v))|u∧ v] =1

(m + M ′ − 1)

∑

ℓ

pℓ.

Substituindo estes valores na desigualdade (3.11) e utilizando o lema 3.2.8 para limitarpℓ,que é o valor esperado da distância entre as classes associadas a dois objetosu ev, considerandoo evento em que ambos os objetos são associados a classes pertencentes ao mesmo intervaloIℓ,temos

E[d(L(u), L(v)] ≤

(1

(m+M ′−1)

∑ℓ

∑e∈CRS(Iℓ)

xe

)M +

(1

(m+M ′−1)

∑ℓ pℓ

)

M ′

(m+M ′−1)

≤ 1

M ′

∑

ℓ

∑

e∈CRS(Iℓ)

xeM +∑

ℓ

pℓ

(3.12)

≤ 1

M ′

∑

ℓ

∑

e∈CRS(Iℓ)

xeM +∑

ℓ

∑

e∈CRS(Iℓ)

eℓxe +∑

e∈INT(Iℓ)

|e|xe

(3.13)

≤ 1

M ′

∑

ℓ

∑

e∈CRS(Iℓ)

(M + eℓ)xe +∑

e∈INT(Iℓ)

|e|xe

(3.14)


≤ 1

M ′

∑

e

xe

∑

ℓ:e∈CRS(Iℓ)

(M + eℓ) +∑

ℓ:e∈INT(Iℓ)

|e|

(3.15)

=∑

e

xede,

ondede = 1M ′ (

∑ℓ:e∈CRS(Iℓ)

(M + eℓ) +∑

ℓ:e∈INT(Iℓ)|e|). A passagem da equação (3.12) para

a equação (3.13) ocorre devido ao lema 3.2.8. As equações (3.14) e (3.15) são equivalentes,dado que na equação (3.14) é considerada primeiro a escolha de ℓ e posteriormente computadaa contribuição doslinks para aquele intervalo. Já na equação (3.15) é considerado umlink ecomputada qual é sua contribuição para todos os intervalos.

O lema 3.2.9 mostra quede é limitado superiormente por(2 + max2M/M ′, M ′/M)de.Isto conclui a prova do lema 3.2.5, levando em consideração quedLP (u, v) =

∑e xede.

Lema 3.2.9 de =1

M ′(

∑

ℓ:e∈CRS(Iℓ)

(M + eℓ) +∑

ℓ:e∈INT(Iℓ)

|e|) ≤ (2 + max

2M

M ′,M ′

M

)de.

Prova.Dado queM ′ ≥M ede ≤M ≤M ′, de é avaliado separadamente para três diferentes tipos

de arestas,|e| ≥M ′, |e| < M eM ≤ |e| < M ′. Sejae = ui, vj um link emH(u, v) e, semperda de generalidade, suponha quei ≤ j. O outro caso é similar.

• |e| ≥ M ′: Neste caso está claro quee não pode ser uma aresta interna de intervalo, paraqualquer intervaloIℓ, ou seja, a contribuição dolink e parade é dada apenas pelo termoda somatória que computa oslinksde cruzamento. Tambémde = M . Assim

M ′de =∑

ℓ:e∈CRS(Iℓ)

(M + eℓ) (3.16)

=∑

ℓ:e∈LCRS(Iℓ)

(M + eℓ) +∑

ℓ:e∈RCRS(Iℓ)

(M + eℓ) (3.17)

=∑

ℓ:e∈LCRS(Iℓ)

(M + M ′ + ℓ− 1− j) +∑

ℓ:e∈RCRS(Iℓ)

(M + M ′ + ℓ− 1− i) (3.18)

=

j∑

ℓ≥j−M ′

(M + M ′ + ℓ− 1− j) +

i∑

ℓ≥i−M ′

(M + M ′ + ℓ− 1− i) (3.19)

≤M ′∑

ℓ=0

(M + M ′ − ℓ) +

M ′∑

ℓ=0

(M + M ′ − ℓ) (3.20)

≤ M ′(2M + M ′)

= M ′(2 + M ′/M)de.


O conjuntoCRS(Iℓ) dos links que cruzam um intervaloIℓ é a união de dois conjuntos,os links LCRS(Iℓ) que cruzam o intervaloIℓ no lado esquerdo e oslinks RCRS(Iℓ) quecruzam o intervaloIℓ no lado direito, justificando a passagem da equação (3.16) para(3.17). A quantidadeeℓ, para uma arestae = ui, vj com i ∈ Iℓ, representa a distânciado vérticeui interno ao intervaloIℓ até o extremo direito do intervaloIℓ, que é igual aM ′ + ℓ− 1− i e aplicando esse valor na equação (3.17) temos a equação (3.18).

Dado umlink e = ui, vj de cruzamento à esquerda, tal quei ≤ j e |i − j| ≥ M ′. Asrestrições da escolha deℓ nos somatórios da equação (3.18) podem ser substituídas porj −M ′ ≤ ℓ ≤ j e i −M ′ ≤ ℓ ≤ i, que são os valores deℓ que mantém olink e comoum link de cruzamento à esquerda e à direita, respectivamente, obtendo assim a equação(3.19).

Claramente o número de possíveis valores queℓ pode assumir éM ′ em ambos somatóriose a diferençaℓ− j, que é a distância do elemento interno ao intervaloIℓ ao limite direitodo intervaloIℓ varia entre0 eM ′, resultando assim na equação (3.20).

• |e| < M : Neste caso olink e pode tanto ser umlink interno quanto umlink de cruzamentoede = |e|.

M ′de =∑

ℓ:e∈CRS(Iℓ)

(M + eℓ) +∑

ℓ:e∈INT(Iℓ)

|e|

=∑

ℓ:e∈LCRS(Iℓ)

(M + eℓ) +∑

ℓ:e∈RCRS(Iℓ)

(M + eℓ) +∑

ℓ:e∈INT(Iℓ)

|e| (3.21)

=

j∑

ℓ>i

(M+M ′+ℓ−1−j)+

j−M ′∑

ℓ>i−M ′

(M+M ′+ℓ−1−i)+i∑

ℓ≥j−M ′

|e| (3.22)

≤|j−i|∑

ℓ=0

(M + M ′ − ℓ) +

|j−i|∑

ℓ=0

(M + ℓ) +

M ′−|j−i|∑

ℓ=0

|e| (3.23)

= |e|M + |e|M ′ − |e| |e|2

+ |e|M + |e| |e|2

+ (M ′ − |e|)|e| (3.24)

= (2M ′ + 2M − |e|)|e|≤ (2M ′ + 2M)|e|= M ′(2 + 2M/M ′)de.

ComoCRS(Iℓ) = LCRS(Iℓ) ∪ RCRS(Iℓ) temos a equação (3.21). Para que olink e =

ui, vj seja umlink de cruzamento à esquerda, o valor deℓ tem que ser maior quei emenor quej. Parae ser umlink de cruzamento à direitaℓ tem que ser entrei −M ′ ej −M ′ e parae ser umlink internoℓ tem que estar entrej −M ′ e i. Utilizando essesvalores paraℓ e substituindo os valores deeℓ, na equação (3.21) temos (3.22).


No primeiro somatório da equação (3.22) temos|j − i| possíveis valores paraℓ fazendocom que os termos do somatório variem deM + M ′ − |j − i|, paraℓ = i + 1, a M +

M ′ − 0− 1, paraℓ = j. No segundo somatórioℓ pode assumir|j − i| valores diferentesfazendo com que os termos do somatório variem deM + 0, paraℓ = i − M ′ + 1, aM + |j− i|, paraℓ = j−M ′. No terceiro somatório temosM ′−|j− i| possíveis valoresparaℓ. Substituindo estes valores na equação (3.22) obtemos a equação (3.23). Como|j − i| = |e|, substituindo e simplificando os somatórios, temos a equação (3.24).

• M ≤ |e| < M ′: Neste caso olink e pode tanto ser umlink interno quanto umlink decruzamento ede = M .

M ′de =∑

ℓ:e∈CRS(Iℓ)

(M + eℓ) +∑

ℓ:e∈INT(Iℓ)

|e|

=∑

ℓ:e∈LCRS(Iℓ)

(M + eℓ) +∑

ℓ:e∈RCRS(Iℓ)

(M + eℓ) +∑

ℓ:e∈INT(Iℓ)

|e|

=

j∑

ℓ>i

(M+M ′+ℓ−1−j)+

j−M ′∑

ℓ>i−M ′

(M+M ′+ℓ−1−i)+

i∑

ℓ≥j−M ′

|e|

≤|j−i|∑

ℓ=0

(M + M ′ − ℓ) +

|j−i|∑

ℓ=0

(M + ℓ) +

M ′−|j−i|∑

ℓ=0

|e|

= |e|M + |e|M ′ − |e| |e|2

+ |e|M + |e| |e|2

+ (M ′ − |e|)|e|= (2M ′ + 2M − |e|)|e|≤ M ′(M ′ + 2M) (3.25)

= M ′(2 + M ′/M)de. (3.26)

Observe que as igualdades e desigualdades anteriores a desigualdade (3.25) são iguais asdesigualdades do caso onde|e| < M . Por conseqüência são válidas. Limitando|e| porM ′ temos a equação (3.25) e como o valor dede = M temos (3.26).

Assim, de acordo com o tamanho dolink, o valorde pode ser(2+M ′/M)de, see = ui, vje |i − j| ≥ M , ou (2 + 2M/M ′)de, see = ui, vj e |i− j| < M . Ou seja o valor dede é nomáximo(2 + max

2MM ′ ,

M ′

M

)de. Este valor nos guia para a escolha deM ′ =

√2M , que é o

valor que minimiza a funçãomax

2MM ′ ,

M ′

M

.

3.2.4 O caso de métricas gerais

Com esta nova formulação Chekuriet al. [7] conseguiram o mesmo fator de aproximaçãode O(log m) para o caso com métrica geral, apresentado anteriormente por Kleinberg e Tar-


dos [17], que utiliza da aproximação do espaço métrico do conjunto de classesL por árvoresmétricasr-HST e aplica o programa linear (KTT) sobre esta aproximação.

A nova formulação serve como uma alternativa na obtenção de uma solução para o problemade classificação com métricas gerais. Em contraste à abordagem dada por Kleinberg e Tardos,Chekuriet al. aplicam diretamente o programa linear (CKNZ) sobre uma instância do problemade classificação métrica.

A solução devolvida pelo programa linear (CKNZ) é usada paraidentificar uma aproxima-ção métrica HST determinística do espaço métrico, de forma que o custo da solução fracionáriadevolvida pelo programa linear (CKNZ) nesta métrica HST seja no máximoO(log m) vezes ocusto do programa linear no espaço métrico original. Isto pode ser feito utilizando o seguinteresultado de Charikaret al.[6], acrescido do resultado de Fakcheroenpholet al.[9].

Proposição 3.2.10Sejad uma métrica arbitrária definida sobrem pontos e sejaα uma funçãonão negativa definida sobre todos os pares de pontos. Entãod pode ser deterministicamenteaproximada por uma árvore métrica HSTT com função de distânciadT tal que

∑

i,j

α(i, j)dT (i, j) ≤ O(log m log log m)∑

i,j

α(i, j)dij.

Dada uma solução do programa linear (CKNZ), aplicamos a proposição 3.2.10 com a funçãode peso

α(i, j) =∑

e=u,v∈E

wexuivj ,

para0 ≤ i, j ≤ m. Isto é,α(i, j) é o peso fracionário da arestae = u, v, ondef(u) = i

e f(v) = j ou f(u) = j e f(v) = i. Como a árvore métrica HST resultante,dT , alteraapenas a métrica entre as classes e não a classificação fornecida pelo programa linear (CKNZ),a solução fracionária continua uma solução factível para esta nova métrica e tem um acréscimono custo de no máximoO(log m). Assim, se arredondarmos a solução fracionária utilizandoamétricadT , acrescentaremos um fator constante no custo da solução e obtém-se um algoritmoO(log m)-aproximado.

Este arredondamento da solução do programa linear (CKNZ) pode ser feito utilizando oalgoritmoAlg_MLde Kleinberg e Tardos, apresentado na figura 3.8, que apresenta um fator deaproximação deO(1) para o problema de classificação métrica, utilizando uma árvore métricaHST para aproximar o espaço métrico das classes, resultandoem um algoritmoO(log m)-aproximado.

Capítulo 4

Algoritmo que Utiliza Fluxo em Redes

Os algoritmos apresentados no capítulo 3 tem como passo inicial a resolução de um pro-grama linear. Neste capítulo apresentaremos uma abordagemdesenvolvida por Gupta e Tar-dos [11], que não depende da resolução de nenhum programa linear para a obtenção de umasolução.

4.1 Fluxo em Redes e os Problemas de Classificação Métrica

Gupta e Tardos [11] apresentam um algoritmo com fator de aproximação constante para o pro-blema de classificação métrica linear truncada,Truncated Line Metric Labeling Problem (TML).No problema TML um conjunto de classesL = 1, . . . , m é visto como um caminho detamanhom onde as classes representam os vértices e as arestas(i, i + 1) entre as classes têmtamanho 1. Para cada par de classesi, j com|i−j| > M é adicionada uma aresta de tamanhoM , resultando assim na métrica linear truncada. Assim a distância entre duas classesi e j édada pelo menor valor entre a diferença, em módulo, entre as classes ou um valor máximoM ,isto é,d : L× L→ N+, d(i, j) = min|i− j|, M. A métrica truncada pode ser vista como ografo da figura 4.1.

1 11 1 1

11 1

MM

MM

M

M

Figura 4.1: GrafoGL para a métrica truncada do conjunto de classesL comM = 5.

O algoritmo apresentado por Gupta e Tardos [11] para o problema TML é um algoritmo de

54

4.1. Fluxo em Redes e os Problemas de Classificação Métrica 55

busca local, e tem fator de aproximação igual a 4. A idéia principal é que o espaço métricotruncado pode ser aproximado por uma árvore estrela gerada aleatoriamente, onde as folhas sãointervalos de tamanho no máximoM . Veja a figura 4.2.

. . . . . . . . .. . .

r+1 i+11 2 3 r r+M m−2 mi+M

M2

M2

M2

M2

Figura 4.2: Árvore de distâncias truncadas, ondei = r+M .

Os passos utilizados para aproximar o grafoGL da métrica truncada (veja a figura 4.1) poruma árvore aleatóriaT (veja a figura 4.2), são os seguintes:

• Escolha aleatoriamente um valorr ∈ 1, 2, . . . , M.

• Para cada posição1 ≤ k ≤ m, tal quek − ⌊ kM⌋M = r, apague cada arestai, j do

grafoGL, ondei ≤ k e j > k (veja a figura 4.2). Como resultado desta operação temosum conjunto de intervalos em função da escolha do valorr, que vamos denotar porSr.Note que apenas o primeiro e o último intervalo podem ter comprimentos menores queM , onde o primeiro intervalo tem tamanho igual ar e o último intervalo tem tamanhoigual a(m− r)− ⌊m−r

M⌋M .

• Crie uma árvore com um nós como sendo a raiz.

• Para cada intervaloI emSr, conecte o menor vértice do intervaloI ao vértices atravésde uma aresta de comprimentoM/2.

Baseado na forma como é construída a árvoreT que aproxima o espaço métrico do conjuntode classesL temos o seguinte fato.

Fato 4.1.1 Para qualquer par de classesi, j ∈ L a probabilidade quei e j pertençam a inter-valos diferentes é igual adij/M .

Como conseqüência deste fato temos o seguinte teorema em relação à distância esperadaentre duas classes na árvoreT .

Teorema 4.1.2Para qualquer par de classesi, j ∈ L a distânciadT (i, j), em qualquer árvoreT aleatória, é no mínimodij e o valor esperado dedT (i, j) é3dij.

56 Capítulo 4. Algoritmo que Utiliza Fluxo em Redes

Prova.Sedij < M e as classesi e j pertencerem ao mesmo intervalo após a escolha der, então a

distância entrei e j é igual adij. No entanto, sei e j pertencem a intervalos diferentes, entãoa distância entre eles será dada pelo menor caminho entre eles, que é no mínimoM . Assim ovalor dedT (i, j) ≥ dij , como anunciado.

Assumindo que as classesi ej são separadas, o valor esperado dedT (i, j) depende de quemvai ser a classe que representa o início do intervalo que contem j, vamos chamar esta classeque é a primeira classe que do intervalo que contemj der2, e vamos chamar der1 a primeiraclasse do intervalo que contem a classei. Note que temosdij possíveis valores parar2, que vaidei + 1 atéi + dij, isto pode ser visto melhor na figura 4.3.

... ... ... ... ... ...

...

... ... ...r2

i j

i jr2

M2

M2

Mdij−1

i j

jr2

M2

M2

dij−2

r2

iM−1

i j

r2

M2

M2

r2

i jM−dij

(a) (b) (c)

Figura 4.3: Possíveis valores dedT (i, j), quandoi e j pertencem a intervalos diferentes.

Denotamos porε o evento ondei e j são separados. O valor esperado dedT (i, j), con-siderando quei e j pertencem a intervalos diferentes, é baseado na probabilidade da escolha der2, que é dado por

E[dT (i, j)|ε] =1

dij

dij∑

i=1

2M − (i− 1) + (dij − i)

=1

dij

dij∑

i=1

2M − (i− 1) + (i− 1)

=1

dij

2Mdij

= 2M.

Assim, o valor esperado dedT (i, j), considerando quei e j pertencem a intervalos dife-rentes, é2M . Como a probabilidade dei e j pertencem a intervalos diferentes édij

M, o valor

esperado dedT (i, j) é dado por


E[dT (i, j)] =dij

M2M +

(1− dij

M

)dij

= 2dij + dij −d2

ij

M≤ 3d(i, j).

Veremos que no algoritmo, esta árvore não é criada diretamente, e sim uma partiçãoSr

aleatória do espaço métrico do conjunto de classes em intervalos, como descrito anteriormente.

4.1.1 O Algoritmo para o Problema TML

O algoritmo apresentado por Gupta e Tardos, que denotamos por Alg_TML_GT, inicia comuma classificação arbitráriaf0, e iterativamente obtém uma nova classificaçãof ′ de menorcusto através de movimentos locais. O movimento local aqui citado consiste em encontrar umanova classificação através da interpretação de cortes em umarede de fluxo, que é construída combase nos custos de associação, separação e as distâncias truncadas, que são aproximadas atravésdas árvores de intervalos, citadas anteriormente. Dada umaclassificaçãof , vamos denotar porQ(f) o seu custo de classificação eQ0 o custo da classificação inicial, ou seja,Q0 = Q(f0).

ALGORITMO Alg_TML_GT(P, L, ǫ)

P := conjunto de objetos; L := conjunto de classes.ǫ := folga de aproximação.

1. Sejaf0 uma classificação aleatória

2. Repitam+MM

(log Q0 + log ǫ−) vezes

3. Escolha aleatoriamente um valorr entre−M em.

4. I ← r + 1, r + 2, . . . , r + M ∩ 1, . . . , m5. Construa a rede de fluxosNI associada ao intervaloI

6. ExecuteMinCut(NI)

7. Sejaf ′ a classificação resultante do corte na rede de fluxos(NI)

8. SeQ(f ′) < Q(f0) então

9. f0 ← f ′

10. Devolvaf0

Figura 4.4: Algoritmo para o caso das distâncias truncadas de Gupta e Tardos.

Na figura 4.4 apresentamos o algoritmoAlg_TML_GTpara o problema de classificaçãométrica linear truncada. O algoritmo começa sua execução com uma classificação arbitrária


f0 e a cada iteração do algoritmo é escolhido aleatoriamente umintervaloI, criada uma redede fluxosNI , que é associada ao intervaloI, e então é aplicado o algoritmo do corte mínimo.Baseado nesse corte é escolhida uma nova classificação para os objetos.

A probabilidade de se escolher umr que dá origem a uma árvore aleatória com um conjuntode intervalosSr é igual a1/M . Dado um conjunto de intervalosSr, a probabilidade de seescolher um intervaloI ′ emSr é igual a1/|Sr|, que é igual aM/m. Assim a probabilidade deum intervaloI ′ ser escolhido é igual a1/m. Note que a probabilidade de escolher um intervaloI, nos passos 3 e 4 do algoritmoAlg_TML_GT, não é maior que a probabilidade de escolher umintervaloI ′ através da escolha de uma árvore aleatória e então, escolhero intervalo no conjuntode intervalos desta árvore.

Antes de fazer a análise do algoritmoAlg_TML_GTvamos ver como é construída a rede defluxosNI e como é obtida uma nova classificação através de um corte mínimo nesta rede.

A rede de fluxosNI é um grafo orientado e sua construção é baseada na relação entre osobjetos e nos custos de associação. Para construir a rede de fluxo, são consideradas as classespertencentes a um intervaloI. Vamos assumir que estas classes sãoi + 1, i + 2, . . . , j, ondeo número de classes é dado por|i − j|, que é no máximoM . A seguir descrevemos a formacomo é construída a rede de fluxoNI associada ao intervaloI.

• Acrescente um vértices como a origem do fluxo et como o destino do fluxo.

• Para cada objetou ∈ P adicione|i− j| nós da formaui+1, . . . , uj.

• Acrescente arestas direcionadas(uk, uk+1) com capacidade igual acuk, para todoi + 1 ≤k ≤ j, ondeuj+1 = t.

• Acrescente arestas direcionadas(uk+1, uk) com capacidade igual a infinito, para todoi + 1 ≤ k ≤ j.

• Acrescente aresta direcionada(s, ui+1) com capacidadeD(u) que é definido como: sef0(u) ∈ I entãoD(u) = ∞, senãoD(u) = c(u, f0(u)), ou seja, a aresta(s, ui+1)

tem capacidade igual a infinito, se a classe a quem o objetou está associado, na atualclassificação, pertencer ao intervaloI, ou a capacidade da aresta(s, ui+1) será igual aocusto da classificação atual do objetou sef0(u) 6∈ I.

• Acrescente uma aresta direcionada(ui+1, s) com capacidade igual a infinito.

A figura 4.5 ilustra uma parte da rede, que se assemelha a uma “corrente”, que é construídapara todos os objetosu ∈ P . Os vérticess e t são criados apenas uma vez, ou seja, todas as“correntes” são ligadas a estes dois vértices.

Para ver a razão dessa construção, considere qualquer cortemínimos−t emNI . A inclusãodas arestas(uk+1, uk), parai + 1 ≤ k ≤ j e (ui+1, s) com pesos igual a infinito, na rede de


s tui+1 ui+3ui+2 uj

D(u) c(u, i + 1) c(u, i + 2) c(u, j)

∞ ∞∞ ∞

Figura 4.5: A “corrente” para o vérticeu.

fluxosNI , faz com que um cortes − t, de capacidade mínima, inclua apenas uma aresta, quepode ser a aresta(s, ui+1) ou uma das arestas(uk, uk+1). Se a aresta que pertencer ao cortemínimos − t for (uk, uk+1), este corte corresponde à associação do objetou com a classek eo seu valor é igual acuk. Já se a aresta(s, ui+1) pertencer ao corte, significa que a classificaçãoanterior deste objeto será mantida. Note que o valor do cortemínimos− t na rede de fluxosNI

representa o custo de associação.Para que o custo de separação seja acrescentado no valor do corte mínimo da redeNI , são

acrescentadas arestas entre as correntes da seguinte forma:

a) Para cada arestae = u, v no grafo original são adicionadas arestas orientadas(uk, vk)

e (vk, uk) cada uma com capacidadewe, ondei + 1 < k ≤ j.

b) Se, na classificação atual,f0(u) ∈ I e f0(v) ∈ I, parae = u, v, então é adicionadauma aresta(ui+1, vi+1) com capacidadewe.

c) Se, na classificação atual,f0(u) 6∈ I e f0(v) ∈ I, parae = u, v, então é adicionadauma aresta(ui+1, vi+1) com capacidadewed(f0(u), i + 1).

d) Se, na classificação atual,f0(u) 6∈ I e f0(v) 6∈ I, parae = u, v, então é adicionadoum novo vérticevuv que é conectado à rede através das arestas(ui+1, vuv) e (vuv, ui+1),ambas com capacidadewed(f(u), i + 1), (vuv, vi+1) e (vi+1, vuv), ambas com capacidadewed(f(v), i + 1) e uma aresta(s, vuv) com capacidadewed(f0(u), f0(v)).

A figura 4.6 ilustra a rede de fluxosNI resultante, para o caso ondef0(u) 6∈ I e f0(v) 6∈ I.Nesta figura as arestas com pesos igual a infinito foram omitidas.

Um cortes−t de capacidade mínima efetuado na redeNI , com as novas arestas, representa,além do custo de associação, o custo de separação. Podemos ter quatro tipos de cortes na redede fluxosNI em relação a dois objetosu e v. Vamos nos referenciar a estes quatro tipos decortes porC1, C2, C3 e C4, assim como ilustrado na figura 4.7. Seguem as características decada tipo de corte e os seus significados.

• Corte do tipoC1: como podemos ver na figura 4.7(a), as arestas que fazem partedestecorte são(uk, uk+1) e(vk, vk+1) que significa que os objetosu ev são associados à mesmaclassek e, por conseqüência, o custo de separação é igual a zero.


s

vuv

ui+1

ui+2

vi+1

vi+2

vjuj

t

we

we

we

we

c(u, i+1) c(v, i+1)

D(u) D(v)

wed(f0(u), f0(v))wed(f0(u), i + 1)

wed(f0(v), i + 1)

c(v, j)c(u, j)

Figura 4.6: RedeNI após o acréscimo das arestas que representam o custo de separação.

s

ui+1 vi+1

ui+2 vi+2

vuv

s

ui+1 vi+1

ui+2 vi+2

vuv

C3

C4

uk

uk−1

uk+1

vk

vk−1

vk+1

C1

vk+1

vk

C2

vhuh

uk+1

uk

(b)

(d)(c)

(a)

Figura 4.7: Exemplos de cortes na redeNI .


• Corte do tipoC2: neste caso, as arestas que fazem parte do corte são(uk, uk+1), (vh, vh+1)

e (vl, ul), parak < l ≤ h, conforme mostra a figura 4.7(b). Como visto anteriormente,as arestas(uk, uk+1) e (vh, vh+1) representam a classificação comf ′(u) = k e f ′(v) = h

com a contribuição para a capacidade do corte decuk e cvh. Já as arestas(vl, ul), parak < l ≤ h, representam o custo de separaçãowed(f ′(u), f ′(v)) = we|k − h|.

• Corte do tipoC3: neste tipo de corte, um dos objetos é associado a uma classe pertencenteao intervaloI e o outro mantém sua classificação anterior. No caso da figura 4.7(c), ocorteC3 indica que o objetou mantém sua associação anterior, ondef0(u) 6∈ I, como custoD(u), que neste caso éc(u, f0(u)), enquanto que o objetov é associado a umaclasse no intervaloI. O custo de separação neste caso éwed(f0(u), i + 1), dado pelaaresta(vuv, ui+1), maiswe|i + 1 − k|, dado pelas arestas(vl, ul), parai + 1 < l ≤ k,supondo que a aresta(vk, vk+1) pertença ao corteC3.

• Corte do tipoC4: como podemos ver na figura 4.7(d), este tipo de corte é composto pelasarestas(s, ui+1), (s, vuv) e (s, vi+1), significando que os objetosu e v mantiveram suaclassificação anterior juntamente com seus custos de associação e separação, que nestecaso é dado porwed(f0(u), f0(v)), pela aresta(s, vuv), maisc(u, f0(u)) e c(v, f0(v)),pelas arestas(s, vuv) e (s, vi+1).

Note que um corte mínimo na rede de fluxosNI corta no máximo uma das arestas entre osvértices(vuv, ui+1), (vuv, vi+1) e (s, vuv). Isto ocorre devido à capacidade de(s, vuv) ser maiorque a soma das capacidades das arestas(vuv, ui+1) e (vuv, vi+1), ou seja,wed(f0(u), f0(v)) ≤wed(f0(u), i+ 1)+ wed(i+ i, f0(v)), o que é verdade devido a função de distância no conjuntode classes ser métrica e respeitar a desigualdade triangular.

Antes de formalizar a relação entre cortes da redeNI e a reclassificação, devemos considerardois casos extremos: (1) quando o intervaloI consiste de todas as classes e (2) quando ointervalo I tem uma única classe,I = i + 1. No caso (1) a construção é a mesma quea apresentada anteriormente e segundo Boykovet al.[4] e Ishikawa e Geiger [13], um cortemínimo na rede de fluxos associada ao intervaloI, que contém todas as classes, equivale àclassificação ótima para a métrica linear emI. No caso (2) a construção da rede continua amesma e o corte indicará quais serão os objetos reclassificados para a classei + 1.

Baseado na forma como é construída a rede de fluxosNI para um intervaloI podemosenunciar o seguinte teorema.

Teorema 4.1.3Os cortes na rede de fluxoNI são um a um correspondentes a uma reclassifi-cação localf ′.

O teorema 4.1.3 segue diretamente da construção da rede de fluxosNI e da interpretaçãodas arestas(uk, uk+1), pertencentes ao corte mínimo, como a associação do objetou à classek.


Lema 4.1.4 Sejaf ′ a classificação resultante de um corte mínimoC na rede de fluxosNI .Para qualquer arestae = u, v do grafo original, a distância, resultante do corteC, entre asclasses associadas au e v é no máximo2M , ou seja,

d(f ′(u), f ′(v)) ≤ d((f ′(u), i + 1) + d(i + 1, f ′(v)) ≤ 2M.

Prova.Na rede de fluxosNI a distância entre duas classes que pertencem ao mesmo intervalo é dada

pelo número de arestas(uk, vk) entre elas. Por exemplo, sef ′(u) = k e f ′(v) = h e k, h ∈ I

então sua distância é dada por|k−h| e, devido à forma como a rede é construída, este valor é nomáximoM . Sef ′(u) 6∈ I ef ′(v) ∈ I então,d(f ′(u), f ′(v)) = d((f ′(u), i+1)+d(i+1, f ′(v)),onded((f ′(u), i+1) é dada pela aresta(s, ui+1) e é limitada porM . A quantidaded(i+1, f ′(v))

é dada por|i+1−f ′(v)|, que também é limitada porM . Assim a distância máxima entref ′(u)

ef ′(v) é2M .

Teorema 4.1.5Sejaf ′ uma classificação resultante de um corte mínimoC emNI . O custo daclassificaçãof ′ não é maior que o custo do corteC.

O teorema 4.1.5 segue diretamente do lema 4.1.4.A cada iteração, a rede de fluxo é reconstruída com base nos custos obtidos na iteração

anterior e é encontrado um novo corte, que representa uma nova classificação. Esta nova clas-sificação será assumida se seu custo for menor que o custo da classificação anterior. A cadaiteração é esperada uma diminuição do custo. O número de vezes em que o laço principal doalgoritmo é executado é obtido analisando a melhora no custode classificação obtida a cada it-eração. Esta melhora implica no fato que quando o algoritmoAlg_TML_GTatingir um mínimolocal, o custo esperado da classificação é de no máximo 4 vezeso custo ótimo.

Para analisar o fator de aproximação deste algoritmo, vamosfixarf ∗ como uma classificaçãoótima, ef como a classificação atual no algoritmoAlg_TML_GT. Para qualquer subconjuntoX ⊆ P , sejaA∗(X) o custo de associação ótimo eA(X) o custo de associação pago pela classi-ficação atual no algoritmo, pago pelos objetos emX. Para o conjunto de arestasY ⊆ E, S∗(Y )

eS(Y ) são os custos de separação ótimo e da classificação atual do algoritmo respectivamente.Claramente o custo da classificação ótima é dado porQ(f ∗) = A∗(P ) + S∗(E) e o custo daclassificação resultante do algoritmo é dado porQ(f) = A(P ) + S(E).

Considere o caso em que o algoritmo escolhe o intervaloI. Dada uma classificação ótimaf ∗, definimos algumas notações relacionadas ao intervaloI e à classificaçãof ∗, que serãoutilizadas na análise do algoritmo.

• PI é o conjunto dos objetos que são associados às classes pertencentes ao intervaloIatravés da função de classificaçãof ∗, ou seja,PI = u : f ∗(u) ∈ I, ∀u ∈ P.


• EI é o conjunto das arestase = u, v ∈ E cujos objetos são associados à classespertencentes ao intervaloI através da função de classificaçãof ∗, ou seja,EI = e =

u, v : f ∗(u) ∈ I, f ∗(v) ∈ I, ∀e ∈ E.

• δ−I é o conjunto das arestase = u, v ∈ E, cuja maior classe associada aos objetos daarestae = u, v, através da função de classificaçãof ∗, pertence ao intervaloI e a menornão, ou sejaδ−I = e = u, v : max(f ∗(u), f ∗(v)) ∈ I, min(f ∗(u), f ∗(v)) 6∈ I, ∀e ∈E.

• δ+I é o conjunto das arestase = u, v ∈ E, cuja menor classe associada aos objetos da

arestae = u, v, através da função de classificaçãof ∗, pertence ao intervaloI e a maiornão, ou sejaδ+

I = e = u, v : min(f ∗(u), f ∗(v)) ∈ I, max(f ∗(u), f ∗(v)) 6∈ I, ∀e ∈E.

I3I2I1

PI3PI1PI2

Figura 4.8: Exemplo de uma classificaçãof ∗ relacionada a um conjunto de intervalosSr.

Para melhor entender as definições anteriores, veja a figura 4.8 que representa uma clas-sificaçãof ∗. Representamos por linhas pontilhadas a classificaçãof ∗ para os objetos. Comopodemos observar, a união de todos os conjuntosPIi

é igual ao conjuntoP . As arestas tracejadassão aquelas arestas cujos objetos são associados a classes que pertencem ao mesmo intervalo,ou seja, são as arestasEI , respectivas a cada intervaloI. As arestas entre os conjuntosPI são asarestas de cruzamento. Note que ao considerarmos o intervalo I2, por exemplo, as arestas queligam objetos dePI2 a objetos emPI1 são as arestas que pertencem ao conjuntoδ−I2 e estas mes-mas arestas fazem parte do conjuntoδ+

I1. Assim fica claro que a união das arestas dos conjuntos

δ−I é igual à união das arestas dos conjuntosδ+I , ou seja,∪I∈Sr

δ−I = ∪I∈Srδ+I . Esta união das

arestas de “fronteira” das partições é denotada porδr. Note também queE = δr ∪ (∪I∈SrEI).

Lema 4.1.6 Para uma partiçãoSr escolhida aleatoriamente, o valor esperado do custo deseparação para as arestas de fronteira,

E

M

∑

e=u,v∈δr

we

, éS∗(E).


Prova.Sejae = u, v uma aresta do grafo original, eεe o evento em que as classes associadas au

ev, através da funçãof ∗, pertençam a intervalos diferentes emSr, ou seja,εe é o evento em quea arestae pertence aδr. A esperança deM

∑e=u,v∈δr

we é igual aM∑

e=u,v∈E wePr[εe].A probabilidade de uma arestae = u, v fazer parte deδr é exatamented(f ∗(u), f ∗(v))/M .Assim

E

M∑

e=u,v∈δr

we

= M∑

e=u,v∈E

we Pr[εe]

= M∑

e=u,v∈E

wed(f ∗(u), f ∗(v))/M

=∑

e=u,v∈E

wed(f ∗(u), f ∗(v))

= S∗(E).

Considere a situação em que o algoritmo escolhe um intervaloI e sejaPI o conjunto deobjetos tal queu ∈ Pi sef(u) ∈ I. Um movimento local de reclassificação possível é trocar aclassificaçãof(u), para todou ∈ PI , pela classificação ótimaf ∗, ou seja,f(u) = f ∗(u), paratodo u ∈ PI . Vamos utilizar este movimento local de reclassificação para limitar a melhoraobtida pelo algoritmo a cada iteração.

Lema 4.1.7 Para uma classificaçãof e um intervaloI, o movimento local de reclassificação,que corresponde a um corte mínimo emNI , decrementa o custo da solução de no mínimo

(A(PI) + S(EI ∪ δ−I ∪ δ+

I ))−

A∗(PI) + S∗(EI ∪ δ−I ) + M∑

e=u,v∈δ−I

we + 2M∑

e=u,v∈δ+I

we

.

Prova.Após o algoritmo ter executado o corte mínimo na rede de fluxosNI , a classificação corres-

pondente a este corte tem custo no máximo o valor do corte.Para provar que a melhora não é superior a anunciada é precisomostrar um corte com

capacidade menor que o corte mínimo emNI . Para tanto, considere um corte que gere o movi-mento local de reclassificação para todos os nós emPI da sua classificação atual para a classifi-caçãof ∗. Esse movimento fará com que o valorA(PI), que é o custo de associação dos objetosemPI , passe a serA∗(PI) e o valorS(EI), que é o custo de separação para as arestas emEI ,passe a serS∗(EI). Para aqueles vértices e arestas que não têm sua classificação alterada nestemovimento os custos de classificação e separação se mantém osmesmos.


Considere as arestas emδ−I ∪δ+I . Estas são as arestas que possivelmente terão a classificação

alterada para exatamente um dos objetos a quem a aresta esta ligada. Para estimar a capacidadedo corte que gerou a nova classificaçãof ∗ para os objetos emPI , correspondente ao custo deseparação destas arestas, vamos considerar as arestas emδ−I e δ+

I separadamente.Usando o lema 4.1.4, o limitante do custo de separação para asarestase = u, v ∈ δ+

I éde2Mwe. Agora, considerando uma arestae = u, v ∈ δ−I , suponha queu ∈ PI . O limitanteda capacidade das arestas emNI pertencentes ao corteC correspondente ao custo de separaçãoda arestae = u, v, pelo lema 4.1.4, éwe[d(f ∗(u), i + 1) + d(i + 1, f(v))]. Note que devido àarestae estar emδ−I temos quef ∗(v) ≤ i e assimd(f ∗(u), i+1) ≤ d(f ∗(u), f ∗(v)). Limitandoo outro termod(i + 1, f(v)) porM obtemos que a capacidade correspondente à separação dosobjetos ligados à arestae = u, v é no máximowe[d(f ∗(u), f ∗(v)) + M ]. Assim temos

A∗(PI) + S∗(EI) +∑

e=u,v∈δ−I

we(d(f ∗(u), f ∗(v)) + M) +∑

e∈δ+I

2Mwe

= A∗(PI) + S∗(EI) +∑

e=u,v∈δ−I

wed(f ∗(u), f ∗(v)) +∑

e=u,v∈δ−I

weM +∑

e∈δ+I

2Mwe

= A∗(PI) + S∗(EI ∪ δ−I ) + M∑

e∈δ−I

we + 2M∑

e∈δ+I

we.

Teorema 4.1.8Se o algoritmo alcançou uma classificaçãof e esta classificação representaum mínimo local, então o custoQ(f) é no máximo4 vezes o custo ótimoQ(f ∗).

Prova.O fato do algoritmo ter alcançado uma classificaçãof que é um mínimo local implica que a

garantia de melhora do lema 4.1.7 neste momento é não positiva para qualquer intervaloI, ouseja,

A(PI) + S(EI ∪ δ−I ∪ δ+I ) ≤ A∗(PI) + S∗(EI ∪ δ−I ) + M

∑

e=u,v∈δ−I

we + 2M∑

e=u,v∈δ+I

we.

Agora, considerando a partiçãoSr e somando estas desigualdades para cadaI ∈ Sr temosdo lado esquerdoA(P ) + S(E) + S(δr), uma vez que as arestas emδr ocorrem nas fronteirasde dois intervalos. Esta quantia é pelo menosQ(f), o custo da classificaçãof . Somando o ladodireito, temos exatamenteA∗(P ) + S∗(E) + 3M

∑e=u,v∈δr

we. Por conseqüência temos

Q(f) ≤ A∗(P ) + S∗(E) + 3M∑

e=u,v∈δr

we,

para qualquer partiçãoSr. Baseado nisso, pode-se obter a esperança do custo de classificação.O lado esquerdo da desigualdade é constante, e pelo lema 4.1.6, o custo esperado do lado direito


é no máximoA∗(P ) + 4S∗(E). Assim temosQ(f) ≤ A∗(P ) + 4S∗(E) ≤ 4Q(f ∗) conformeanunciado.

Teorema 4.1.9SejaQ0 o custo da classificação inicial. Se o laço principal do algoritmoAlg_TML_GT for repetidoO((m/M)(log Q0 + log ǫ−)) vezes, então o custo esperado da clas-sificação resultante é no máximo(4 + ǫ)Q(f ∗).

Prova.Para estimar o decréscimo esperado do custo de classificaçãoem uma iteração, considere

a seguinte alternativa para seleção aleatória de um intervalo. Primeiro, selecione aleatoria-mente uma partiçãoSr e em seguida selecione um intervaloI ∈ Sr. Este processo selecionacada intervalo, para ser usado pelo algoritmoAlg_TML_GT, com aproximadamente a mesmaprobabilidade, a diferença é que algumas partições têm um intervalo a mais que outras, e aprobabilidade de escolher um intervalo nestas partições é menor.

Considerando uma classificaçãof , uma partiçãoSr e a escolha do intervaloI, o lema 4.1.7 éusando para estimar um limitante da melhoria obtida para o intervaloI. Como na prova anterior,é somada a estimativa de melhora para todos os intervalos da partiçãoSr.

Como há no máximo⌈m/M⌉ + 1 intervalos emSr, o decréscimo esperado no custo daclassificação, quando um intervalo é selecionado aleatoriamente deSr, é pelo menos

1

⌈m/M⌉+ 1

Q(f)−Q(f ∗)− 3M

∑

e=u,v∈δr

we

.

Mas pelo lema 4.1.6, para uma partiçãoSr escolhida aleatoriamente, o valor esperado dessedecréscimo é pelo menos

Ω

(M

m(Q(f)− 4Q(f ∗))

),

assim, emO(m/M) iterações é esperada que a diferençaQ(f)− 4Q(f ∗) decresça por um fatorconstante. Isto implica no limite do tempo de execução anunciado.

Capítulo 5

Algoritmo Guloso para o Problema deClassificação Métrica Uniforme

Neste capítulo apresentamos um novo algoritmo, que é experimentalmente polinomial, parao problema de classificação métrica uniforme UML. A idéia utilizada na criação deste algoritmosurgiu do estudo de problemas correlatos, como o problema delocalização de recursos e oproblemas da cobertura por conjuntos. Antes de mostrar o novo algoritmo, vamos apresentaruma prova de um fator de aproximação de um algoritmo guloso, para o problema de coberturapor conjuntos, via uma análise primal-dual, em seguida mostraremos uma abordagem para oproblema de localização de recursos, que serviu de inspiração para o desenvolvimento destenovo algoritmo. Também, mostraremos uma família de instâncias cujo o fator de aproximaçãoéΩ(log n).

5.1 Uma Análise Primal-Dual para o Problema de Coberturapor Conjuntos

Nesta seção apresentamos uma versão primal-dual para um algoritmo aproximado guloso parao problema de cobertura por conjuntos, incluindo uma prova de seu fator de aproximação. Estaversão primal-dual difere da maioria dos algoritmos primal-duais por usar uma atribuiçãoα, quepode ser dual inviável, e no final busca um valorγ, tal que,α/γ seja uma solução dual viável.Apresentamos, também, nesta seção uma generalização da prova para o algoritmo primal-dualpara o caso em que os custos dos conjuntos sejam aproximados.

Uma instância para o problema de Cobertura por Conjuntos Mínima (MinCC) é compostade um conjuntoESC = e1, e2, . . . , en, den objetos, uma coleçãoSSC = C1, . . . , Ct, desubconjuntos deESC, e uma função de custow : SSC → Q+. O objetivo é encontrar umacoleçãoSSC

′ ⊆ SSC, tal que∪Ci∈SSC′Ci = ESC, que minimize

∑Ci∈SSC

′ w(Ci).

67

68 Capítulo 5. Algoritmo Guloso para o Problema de Classificação Métrica Uniforme

Um algoritmo guloso clássico para o problema de cobertura por conjuntos é apresentadopor Chvátal [8], e é umaHg-aproximação, ondeg é o número de elementos do maior conjuntoemSSC e Hg é o valor do número harmônico de graug. Neste algoritmo temos um conjuntoU dos elementos “não cobertos”, que são aqueles que não pertencem a qualquer conjunto quejá esteja na solução. Inicialmente o conjuntoU contém todos os elementos. A cada iteração oalgoritmo escolhe um conjuntoCj ∈ SSC que tenha o menor custo amortizado, que é o custowj do conjuntoCj dividido pelo número de elementos “não cobertos”, ou seja,wj

Cj∩U. Uma vez

que um conjunto é escolhido para fazer parte da solução, todos os elementos deste conjuntosão considerados “cobertos” e então removidos do conjuntoU . Na figura 5.1 descrevemos estealgoritmo mais formalmente.

ALGORITMO Alg_GCC(ESC,SSC, w)

ondeESC é um conjunto de elementos,SSC é uma família deconjuntos e

w é o custo dos conjuntos.

11. Sol ← ∅; U ← ESC.

12. EnquantoU 6= ∅ faça

13. j′ ← arg minj:Cj∩U 6=∅wj

|Cj∩U |

14. Sol ← Sol ∪ j′15. U ← U \ Cj′

16. DevolvaSol .

Figura 5.1: Algoritmo guloso para o problema de cobertura por conjuntos.

Para mostrar o algoritmo primal-dual para o problema de cobertura por conjuntos, apre-sentaremos primeiramente uma formulação que usa variáveisbináriasxj , para cada conjuntoCj ∈ SSC, ondexj = 1, se e somente se,Cj é escolhido para entrar na solução. A formulaçãoconsiste em encontrarx que

min∑

j

wjxj

s.a∑

j:e∈Cj

xj ≥ 1 ∀ e ∈ ESC,

xj ∈ 0, 1 ∀ j ∈ 1, . . . , t,

e o dual da versão relaxada consiste em encontrarα que

min∑

e∈ESCαe

s.a∑

e∈Cjαe ≤ wj ∀ j ∈ 1, . . . , t,

αe ≥ 0 ∀ e ∈ ESC.

5.1. Uma Análise Primal-Dual para o Problema de Cobertura por Conjuntos 69

O algoritmo guloso pode ser reescrito como um algoritmo primal-dual com um conjuntosimilar de eventos onde os elementos são inseridos na solução na mesma ordem. Para rees-crevermos o algoritmo usaremos um conjuntoU , que contém os elementos não cobertos, ini-cialmente igual ao conjuntoESC. A cada iteração, o conjuntoU é atualizado removendo-se oselementos “cobertos” na iteração. Além do conjuntoU , usaremos uma variávelT , para expres-sar a noção de tempo associado a cada evento, e usaremos variáveis duaisαe, associadas a cadaelementoe ∈ ESC. As variáveisαe têm seus valores iniciais iguais a zero e são aumentadasuniformemente a cada iteração, juntamente com a variávelT . O algoritmo primal-dual estáilustrado na figura 5.2.

ALGORITMO Alg_PDCCESC,SSC, w)

ondeESC é um conjunto de elementos,SSC é uma família deconjuntos e

w o custo dos conjuntos.

1. U ← ESC; T ← 0 ; αe ← 0, ∀e ∈ ESC; Sol ← ∅.2. EnquantoU 6= ∅ faça

3. Aumente uniformemente o tempoT e as variáveisαe : e ∈ U

até existir um índicej tal que∑

e∈Cj∩U αe seja igual awj.

4. Sol ← Sol ∪ j.5. U ← U \ Cj.

6. DevolvaSol .

Figura 5.2: Algoritmo primal-dual para o problema de cobertura por conjuntos.

Lema 5.1.1 A seqüência de eventos executada pelo algoritmo guloso Alg_GCC e pelo algo-ritmo Primal-Dual Alg_PDCC é a mesma.

Prova.Note que o valor deαe quando

∑e∈Cj∩U αe = wj é igual ao custo amortizado do con-

juntoCj . Desde queαe cresça uniformemente, no passo 3 do algoritmoAlg_PDCC, o algoritmoescolhe o conjunto com menor custo amortizado em cada iteração.

Este lema indica que todas as soluções obtidas pelo algoritmo guloso podem ser analisadasatravés da técnica primal-dual associada ao algoritmoAlg_PDCC.

Lema 5.1.2 SejaCj = e1, e2, . . . , ek e αi a variável de tempo associada ao itemei, obtidano final do algoritmo primal-dual. Seα1 ≤ α2 ≤ . . . ≤ αk, então em um instanteαl, para todo1 ≤ l ≤ k,

∑k

i=l αl ≤ wj .


Prova.No momento exatamente anterior ao tempoαl, todas as variáveisαi, l ≤ i ≤ k tem o mesmo

valor,αl, e todas elas são associadas a um elemento não coberto. Suponha que o lema é falso.Neste caso,

∑k

i=l αl > wj e em um instante imediatamente anterior aαl, o conjuntoCj deveriater entrado na solução e todos os seus elementos deveriam terα < αl, o que é uma contradição,já queCj tem pelo menos um elemento maior ou igual aαl. Assim, o lema é válido.

α1 α2 αk

αl

α3 αl

Figura 5.3: Exemplo dos valores deα no momentoαl.

O algoritmo primal-dual devolve uma solução primalSol , de custoval(Sol) =∑

e∈E αe,que é viável e inteira. Note que uma soluçãoα pode ser dual inviável, devido ao passo 3 doalgoritmoAlg_PDCCaumentar apenas as variáveisαe cujo elementoe não tenha sido cobertoainda até que

∑e∈Cj∩U αe = wj , fazendo com que a restrição

∑e∈Cj

αe ≤ wj possa ser violada.Se existir um valorγ tal queα/γ é dual viável, ou seja,

∑e∈Cj

αe/γ ≤ wj, para cadaj ∈1, . . . , t, então, pelo teorema forte da dualidade,val(Sol) ≤ γ OPT . A idéia usada paraprovar o fator de aproximação é encontrar um valorγ tal queα/γ seja dual viável.

Teorema 5.1.3O algoritmo primal-dual para o problema de cobertura por conjuntos é umalgoritmoHg-aproximado, ondeg é o tamanho do maior conjunto emSSC e Hg é o valor donúmero harmônico de graug.

Prova.Considere um conjunto arbitrárioC = e1, . . . , ek, comk elementos e com custow. Cada

elementoei ∈ C possui uma variável de tempoαi associada, parai = 1, . . . , k. Sem perda degeneralidade , assuma queα1 ≤ . . . ≤ αk.

Seγ é um valor tal queα/γ é dual viável então

k∑

i=1

αi/γ ≤ w, (5.1)

assim, uma condição necessária é

γ ≥∑k

i=1 αi

w. (5.2)

5.1. Uma Análise Primal-Dual para o Problema de Cobertura por Conjuntos 71

Aplicando o lema 5.1.2 para cada valor del, temos

l = 1, kα1 ≤ w, ⇒ α1/w ≤ 1/k,

l = 2, (k − 1) α2 ≤ w, ⇒ α2/w ≤ 1/(k − 1),...

l = k, αk ≤ w, ⇒ αk/w ≤ 1.

Somando as desigualdades acima temos∑k

i=1 αi

w≤ Hk. (5.3)

Conseqüentemente, quandoγ = Hg temos queα/γ é uma solução dual viável.

Uma instância que mostra que este fator de aproximação é justo está ilustrada na figura 5.4.Nesta instância temosn elementosESC = e1, e2, . . . , en, e n + 1 conjuntos que pertencema família de conjuntosSSC = C1, . . . , Cn+1, onde a composição dos conjuntos é a seguinte:C1 = e1, C2 = e2, . . . , Cn = en e Cn+1 = e1, e2, . . . , en com os custos1

n, 1

n−1, . . . ,

12, 1, e1 + ǫ respectivamente.

1n

1+ǫ

11n−1

. . .

Figura 5.4: Instância justa para o algoritmoAlg_PDCC.

Quando executamos o algoritmoAlg_PDCCsobre esta instância a solução devolvida é com-posta dosn conjuntos unitários. Assim o custo da solução devolvida pelo algoritmo é

1

n+

1

n−1+ . . . + 1 = Hn,

enquanto que o custo da cobertura ótima é1 + ǫ.Agora, considere uma pequena modificação no algoritmoAlg_GCC. No passo 3 do algo-

ritmo guloso, ao invés de escolher o conjunto com menor custoamortizado, passamos a escolherum conjuntoCj com custo amortizado no máximof vezes maior que o custo de um conjunto demenor custo amortizado. SeCj∗ é um conjunto com o menor custo amortizado então a seguintedesigualdade é válida.

wj

|Cj ∩ U | ≤ fwj∗

|Cj∗ ∩ U | .

Esta modificação permite que o custo amortizado do conjunto escolhido seja no máximofvezes maior que o menor custo amortizado de um conjunto. Denotamos porAf o algoritmoprimal-dual com esta modificação.


Lema 5.1.4 SejaCj = e1, e2, . . . , ek e αi a variável de tempo associada ao itemei geradapelo algoritmoAf . Seα1 ≤ α2 ≤ . . . ≤ αk então em um instanteαl, para todo1 ≤ l ≤ k,∑k

i=l αl ≤ f wj.

Prova.Suponha por contradição que o lema é falso. Neste caso, existe uma execução onde∑k

i=l αl > f wj e, em um instanteT < αl, o conjuntoCj teria sido escolhido para entrarna solução impedindo que os valores deαi chegassem ao valorαl ou maior, o que é uma con-tradição.

Teorema 5.1.5Seg é o tamanho do maior conjunto emSSC, então o algoritmoAf é umalgoritmof Hg-aproximado.

Prova.Considere um conjunto arbitrárioC = e1, . . . , ek, comk elementos e com custow. Cada

elementoei ∈ C possui uma variável de tempoαi associada, parai = 1, . . . , k. Pela descriçãodo algoritmoAf , a soma

∑e∈C αe pode ultrapassar o valor dew por no máximo um fator def .

Sem perda de generalidade, assuma queα1 ≤ . . . ≤ αk.Seγ é um valor tal queα/γ é dual viável então

k∑

i=1

αi/γ ≤ w, (5.4)

assim, uma condição necessária é

γ ≥∑k

i=1 αi

w. (5.5)

Aplicando o lema 5.1.4 para cada valor del, temos

l = 1, kα1 ≤ f · w, ⇒ α1/w ≤ f · (1/k),

l = 2, (k − 1) α2 ≤ f · w, ⇒ α2/w ≤ f · (1/(k − 1)),...

l = k, αk ≤ f · w, ⇒ αk/w ≤ f · (1).

Somando as desigualdades acima temos∑k

i=1 αi

w≤ f ·Hk. (5.6)

Conseqüentemente, quandoγ = f ·Hg temos queα/γ é uma solução dual viável. Assim, peloteorema forte da dualidade, o algoritmoAf é um algoritmof Hg-aproximado.

5.2. O Problema de Localização de Recursos 73

5.2 O Problema de Localização de Recursos

A idéia que inspirou um novo algoritmo para o problema de classificação métrica uniformesurgiu ao estudarmos um algoritmo apresentado por Jainet al. [14], para o problema de locali-zação de recursos, que utiliza a idéia de estrelas. Umaestrelaé um grafo conexo onde apenasum vértice, chamado centro da estrela, pode ter grau maior que um e um conjunto de estrelas édenominadoconstelação. A figura 5.2 ilustra um conjunto de estrelas.

Figura 5.5: Conjunto de estrelas.

Uma estrela, para o problema de localização de recursos, é composta por um recurso, queé o nó central, e os clientes atendidos por este recurso. Já uma estrela para o problema declassificação métrica é formada por uma classe, que é o nó central, e os objetos classificadoscomo pertencentes a esta classe.

A idéia de estrelas no problema de localização de recursos surgiu com um algoritmo de Jaine Vazirani [15], que é baseado na análise da formulação dual do problema de localização derecursos. Uma solução para o problema de localização de recursos é um par(I, φ), ondeI ⊆ F

é o conjunto dos recursos abertos eφ(j) é uma função que indica o recurso emI que atende oclientej.

Jainet al. [14] apresentam uma forma de resolver o problema de localização de recursosutilizando a idéia de estrelas, semelhante à usada por Jain eVazirani [15]. O algoritmo é iterativoe trabalha de forma gulosa, escolhendo sempre a estrela de menor custo amortizado. O custoamortizado de uma estrela, para o problema de localização derecursos, é dado pela relaçãoentre o custo da estrela e o número de clientes atendidos por ela. O custo de uma estrela édado por dois fatores: o custo de abrir o recurso e o custo de atender os clientes usando aquelerecurso. Mais formalmente, o custo de uma estrela(i, C ′), ondei é o recurso eC ′ ⊆ C é umsubconjunto de clientes, é dado pelo valorfi +

∑j∈C′ cij. O custo amortizado de uma estrela

(i, C ′) é a razão entre o custo da estrela e o tamanho deC ′, ou seja,(fi +∑

j∈C′ cij)/|C ′|.Na descrição do algoritmo de Jainet al. [14], que chamamos porAlg_SFL, denotamos por

U o conjunto dos clientes não atendidos por nenhum recurso, por SFLP o conjunto de todas asestrelas para o conjuntoU , porA o conjunto dos recursos abertos e porφ a função de conexãode um cliente a um recurso. O algoritmo de Jainet al. [14] é apresentado na figura 5.6.

Se observarmos os passos 4 e 5 do algoritmoAlg_SFL, onde são geradas todas as estrelaspara o conjuntoU e entre estas estrelas é escolhida uma de menor custo efetivo, podemos


ALGORITMO Alg_SFL(G)

ondeG é um grafo bipartido(F, C).

1. A← ∅2. U ← C

3. EnquantoU 6= ∅4. SFLP← (i, C) : C ⊆ U, i ∈ F5. Escolha uma estrelaS = (i, C ′) de menor custo amortizado emSFLP

6. Sei 6∈ A

7. Pague o custofi

8. A← A ∪ fi

9. fi ← 0

10. Para todoj ∈ C ′ faça

11. φ(j) = i

12. U ← U\C ′

13. Devolva(A, φ)

Figura 5.6: Algoritmo guloso para o problema de localizaçãode recursos usando estrelas.

concluir que em princípio o algoritmoAlg_SFLpossui tempo de execução exponencial. Istoocorre porque cada cliente pode ou não estar ligado a um recurso, assim temos que o númerode estrelas com pelo menos um cliente énf ∗ (2nc − 1), ondenf é o número de recursos enc éo número de clientes.

Observando uma solução para uma instância do problema, temos que apenas as estrelas demenor custo amortizado são utilizadas. Portanto, se for possível encontrar apenas as estrelas demenor custo amortizado em tempo polinomial, o algoritmoAlg_SFLserá polinomial. Jainetal. [14], observaram que apenas os clientes mais próximos são atendidos pelo recursoi, ou seja,a estrela de menor custo amortizado é formada por aqueles clientes que têm menor custo deassociação. A figura 5.7 mostra um exemplo de estrela formadapelos clientes mais próximos,o que resulta no menor custo amortizado.

Figura 5.7: Exemplo de estrela de menor custo amortizado.

Uma forma de encontrar as estrelas de menor custo amortizado, para um recursoi ∈ F , éordenar os custos de associaçãocij , para todoj ∈ C. Sem perda de generalidade, considere

5.3. Um Algoritmo Primal-Dual para o Problema de Classificação Métrica Uniforme 75

ci1 ≤ ci2 ≤ . . . ≤ cin, e escolha osk clientes que possuem os menores custoscij, tal queo valor da equação(fi +

∑k

j=1 cij)/k seja minimizado. Como a ordenação e a escolha dosk menores elementos pode ser feita em tempo polinomial, a escolha de uma estrela de menorcusto amortizado pode ser feita em tempo polinomial. Conseqüentemente há uma maneira deimplementar o algoritmoAlg_SFLdescrito de forma que este consuma tempo polinomial.

5.3 Um Algoritmo Primal-Dual para o Problema de Classifi-cação Métrica Uniforme

O algoritmo que apresentaremos para o problema de classificação métrica uniforme, usa umaidéia similar ao algoritmo apresentado por Jainet al.[14] para o problema de localização derecursos, apresentado na seção anterior. No problema de classificação métrica podemos consi-derar uma classificaçãof : P → L como um conjunto de estrelas, onde cada estrela é formadapor uma classe, que é nó central, e os objetos associados a esta classe. Uma estrelaS para oproblema de classificação métrica uniforme é uma tupla(l, US), ondel ∈ L e US ⊆ P . Onovo algoritmo para o problema de classificação métrica uniforme seleciona a cada iteraçãouma estrela de menor custo amortizado, até que todos os objetos tenham sido classificados.

O custoC(S) de uma estrelaS = (l, US), ondel ∈ L eUS ⊆ P , é definido como

C(S) = c(US) +1

2w(US),

ondec(US) =∑

u∈UScul e w(US) =

∑u∈US ,v∈(P\US) wuv, que é o custo de associar cada

elemento deUS à classel somado com metade do custo de separar cada objeto deUS dosobjetos emP \ US. É considerada apenas a metade do custo de separação porque aoutrametade será considerada quando os objetos emP \ US forem associados a alguma estrela.

A figura 5.8 ilustra uma instância para o problema de classificação métrica uniforme e afigura 5.9 ilustra todas as possíveis estrelas e seus custos para esta instância.

Os principais passos do algoritmo consistem em:

a) Gerar estrelas de menor custo amortizado para todas as classes;

b) Escolher entre todas as estrelas geradas uma estrela de menor custo relativo;

c) Associar os objetos pertencentes a esta estrela à respectiva classe;

d) Remover os objetos associados na iteração do conjunto dos objetos considerados;

e) Repetir os passos acima até que todos os objetos tenham sido classificados.


ClassesObjetos

j

v

y

i

22

61

3

34

5

u

2

Figura 5.8: Uma instância para o problema UML.

j

u

w = 7, 5

j

v

w = 3

j

y

w = 6, 5

i

y

w = 6, 5

i

v

w = 8

i

u

w = 5, 5

j

u y

w = 9

j

u v

w = 8, 5

j

v y

w = 7, 5

i

u y

w = 7

i

v y

w = 12, 5

j

u v y

i

u v y

w = 11 w = 8

i

u v

w = 11, 5

Figura 5.9: Todas as estrelas da instância apresentada na figura 5.8.

A busca por estrelas de menor custo amortizado é resolvida através de um algoritmo parao problema de cobertura por conjuntos. Para isso é preciso mapear as estrelas, geradas para oproblema de classificação métrica uniforme, em uma instância para o problema de coberturapor conjuntos.

A transformação do conjunto de todas as possíveis estrelasS, de uma instância do problemade classificação métrica uniforme, em uma instância(ESC,SSC, w′) do problema de cobertura


por conjuntos pode ser feita da seguinte forma:

• O conjuntoESC, dos elementos a serem cobertos, é igual ao conjuntoP de objetos.

• A família de conjuntosSSC = C1, . . . , Ct é formada pelas estrelasS, ondeS = (l, US),para todol ∈ L eUS ⊆ P .

• O custow′i de cada conjuntoCi ∈ SSC é o custo da estrelaS = (l, US) que originou o

conjuntoCi.

A instância para o problema UML, apresentada na figura 5.8, e as estrelas para esta instância,apresentadas na figura 5.9, geram uma instância para o problema de cobertura por conjuntos,onde o conjunto de elementosESC é igual au, v, y e a coleção de conjuntosSSC pode servista na figura 5.10.

u y

w′ = 9

u v

w′ = 8, 5

v y

w′ = 7, 5

u y

w′ = 7

v y

w′ = 12, 5

u v

w′ = 11, 5

i i i j j j

i i i j j j

i j

u

w′ = 7, 5

v

w′ = 3

y

w′ = 6, 5

y

w′ = 6, 5

v

w′ = 8

u

w′ = 5, 5

u v yu v y

w′ = 11 w′ = 8

Figura 5.10: Todos os conjuntos gerados pelas estrelas apresentadas na figura 5.9.

Na figura 5.11 é apresentada a descrição do algoritmo guloso para o problema de classi-ficação uniforme, GUL, que usa um algoritmo aproximado para o problema de cobertura porconjuntos. Assumimos que um dos parâmetros de entrada do algoritmo GUL é o algoritmoaproximado para o problema de cobertura por conjuntos que será utilizado no algoritmo. Nadescrição do algoritmo GUL usamos a seguinte notação:

• SULP é o conjunto de todas as possíveis estrelas;

• U é o conjunto dos objetos não classificados;

• (ESC,SSC, w′) é uma instância para o problema de cobertura por conjuntos;

• U é uma coleção de conjuntos de objetos;

• f é uma classificação.


ALGORITMO GREEDY UNIFORM LABELING (GUL ) (P, L, d, c, w,ASC)

onde(P, L, d, c, w) é uma instância para o problema UML eASC é um algoritmoβ-aproximado para o problema de cobertura

por conjuntos.

1. ESC← P.

2. SSC← US : S = (l, US) ∈ SULP.3. w′

S ← CS + 12w(US), ∀ S = (l, US) ∈ SULP.

4. U ← ASC (ESC,SSC, w′), seja U = US1 , US2, . . . , USt.

5. U ← P.

6. Parak ← 1 atét faça

7. Sejal ∈ L a classe associada comUSk;

8. f(i)← l, ∀i ∈ USk∩ U ;

9. U ← U \ USk.

10. devolvaf .

Figura 5.11: Novo algoritmo para o problema de classificaçãométrica uniforme.

5.3.1 Análise do Algoritmo

Para analisar o algoritmo usaremos a seguinte notação:

• valULP(f) é o valor, no problema de classificação métrica uniforme, da classificaçãof ;

• valSC(U) é o valor, no problema de cobertura por conjuntos, da coleçãoU ;

• fOPT é uma classificação ótima para o problema de classificação métrica uniforme;

• UOPT é uma solução ótima para o problema de cobertura por conjuntos;

• SC(f) é uma coleçãoUS1 , US2, . . . , USk relacionada com uma classificaçãof = S1, S2,

. . . , Sk, ondeSi = (l, USi) é uma estrela.

Lema 5.3.1 Sef é uma solução devolvida pelo algoritmoGUL eU é a solução devolvida peloalgoritmoASC para o problema de cobertura por conjuntos (no passo 4) então

valULP(f) ≤ valSC(U).

Prova.


valULP(f) =∑

S∈f

C(S) =∑

S∈f

(c(US) +

1

2w(US)

)(5.7)

≤∑

US∈U

(c(US) + w(US)) (5.8)

=∑

US∈U

(C(S) +

1

2w(US)

)

=∑

US∈U

w′S = valSC(U)

A igualdade (5.7) é válida, já que as estrelas emf são disjuntas, isto pode ser checado porcontagem. A desigualdade (5.8) é válida, já que um custo de associação devalULP(f) tambémaparece emvalSC(U), ∑

S∈f

c(US) ≤∑

US∈U

c(US),

e o custo de separaçãowuv, para qualqueru ev, ondef(u) 6= f(v), que aparece emvalULP(f)

deve aparecer, uma ou duas vezes, emvalSC(U),

∑

S∈f

1

2w(US) =

∑

u<v:f(u)6=f(v)

wuv ≤∑

US∈U

w(US).

Lema 5.3.2 valSC(UOPT) ≤ 2valULP(fOPT).

Prova.

2valULP(fOPT) = 2∑

S∈fOPT

C(S) ≥∑

S∈fOPT

(C(S) +

1

2w(US)

)(5.9)

=∑

t∈SC(fOPT)

w′t

≥∑

t∈UOPT

w′t (5.10)

= valSC(UOPT),

onde a desigualdade (5.9) é válida, já queC(S) ≥ 12w(US). A a desigualdade (5.10) é válida,

já queSC(fOPT) é uma solução para o problema cobertura por conjuntos, mas não necessaria-mente com valor ótimo.


Teorema 5.3.3SeI é uma instância para o problema UML,f é a classificação gerada peloalgoritmoGUL efOPT é uma classificação ótima paraI então

valULP(f) ≤ 2β valULP(fOPT),

ondeβ é o fator de aproximação do algoritmoASC dado como parâmetro.

Prova.SejaU a solução devolvida pelo algoritmoASC (passo 4 do algoritmo GUL) eUOPT uma

solução ótima para a instância do problema de cobertura por conjuntos correspondente. Nestecaso temos

valULP(f) ≤ valSC(U) (5.11)

≤ β valSC(UOPT) (5.12)

≤ 2β valULP(fOPT), (5.13)

onde a desigualdade (5.11) é válida pelo lema 5.3.1, a desigualdade (5.12) é válida já queU éencontrada por um algoritmoβ-aproximado e a desigualdade (5.13) é válida pelo lema 5.3.2.

Para obter um algoritmo polinomial que é8 log n-aproximado para o problema UML pre-cisamos apresentar um algoritmoASC que seja4 log n-aproximado para o problema de cober-tura por conjuntos e que não precise de todas as possíveis estrelas. O algoritmo é baseado emuma aproximação para o problemaQuotient Cut, que é descrito a seguir.

5.3.2 Um Algoritmo ASC polinomial para o problema de cobertura porconjuntos

O conjunto de todas as possíveis estrelas e, por conseqüência, a coleção de conjuntosSSC dalinha 2 do algoritmo possui tamanho exponencial e a geração de todos os conjuntos tornarianosso algoritmo inviável. Nesta seção mostraremos como implementar o algoritmo guloso parao problema de cobertura por conjuntos sem gerar todos os possíveis conjuntos.

Os passos de 1 a 4 do algoritmo GUL , que dizem respeito a transformação de uma instânciado problema de classificação métrica em uma instância do problema de cobertura por conjuntos,através da criação de todas as estrelas possíveis, devem sersubstituídos por um algoritmo queencontra as estrelas de menor custo amortizado que serão usadas no problema de cobertura porconjuntos. Este novo algoritmo basicamente gera um grafoGl para cada possível classel ∈ L

e obtém um conjuntoUS de menor custo amortizado referente à classel.Em uma dada iteração para encontrar o conjuntoUS que minimizewS/|US ∩ U |, ondeU é

o conjunto dos objetos não cobertos, é construído um grafo completoGl da seguinte forma:


a) O conjunto dos vérticesV (Gl) = P ∪ l, ondeP é o conjunto dos objetos el é umaclasse deL;

b) O pesowGl(u, v) das arestase = u, v no grafoGl, parae = u, v ∈ U , é igual awe e

o pesowGl(u, l) para as arestas(u, l), ondeu ∈ U é igual acul.

Em outras palavras, o custo de uma aresta entre uma classe e umobjeto é o custo de associaçãoe o custo de uma aresta entre dois objetos é o custo de separação.

Lema 5.3.4 SeC ⊆ P é um corte deGl, l /∈ C, o custo do corteC, c(C) =∑

u∈C,v 6∈C wGl(u, v),

é igual ao custo da estrelaS = (l, C) para o problema de cobertura por conjuntos.

Prova.O lema pode ser provado por contagem. No problema de cobertura por conjuntos,wS é

igual a ∑

u∈US

cul +∑

u∈US ,v∈P\US

wuv, onde S = (l, US),

que é igual ao custo do corteC. Veja a figura 5.12.

l

C

P

u∈C cul

P

j∈C,i∈(P\C) wij

C ∩ P

Figura 5.12: Exemplo de um corteC que tem o mesmo custow′S paraUS = C.

Vimos que o custo do corte no grafoGl equivale ao custo da estrelaS. Gostaríamos que arazão entre o custo do corteC e o número de elementos do corteC fosse mínima. Isto pode serresolvido pelo problemaQuotient Cut[18], definido a seguir.

Definição 5.3.5QUOTIENT CUT PROBLEM (QCP): Dado um grafoG com pesowe ∈ R+

para cada arestae ∈ E(G) e pesoc(v) ∈ Z+ para cada vérticev ∈ V (G). O objetivo éencontrar um corteC que minimizew(C)/ minπ(C), π(C), ondew(C) :=

∑u∈C,v 6∈C wuv e

π(C) :=∑

v∈C c(v).


Se definirmos uma função de pesocl para cada vértice deGl como

cl(v) =

1 sev ∈ V (Gl) ∩ P ∩ U,

0 sev ∈ V (Gl) ∩ (P \ U),

n sev ∈ V (Gl) ∩ L,

ondeU são os objetos não classificados, então um corteC := mini∈LQC(Gl, wGl, cl), de-

volvido por um algoritmoQC f -aproximado para o problemaQuotient Cut, corresponde a umconjuntoS, S = l ∪ C que é no máximof vezes maior que o conjunto com o custo amor-tizado mínimo. Um algoritmoAf pode ser implementado escolhendo este conjunto. Assim, oseguinte resultado é válido pelo teorema 5.1.5.

Teorema 5.3.6Se existir um algoritmof -aproximado para o problema Quotient Cut com tempode execuçãoT (n), então existe um algoritmo2f Hn-aproximado para o problema UML, comcomplexidade de tempo igual aO(n m T (n)).

O problemaQuotient Cuté NP-difícil e Aumann e Rabani [1] apresentam um algoritmopolinomialO(logn)-aproximado para o problema. Mais recentemente Freivalds [10] apresen-tou uma algoritmo com fator de aproximação4 para o problemaQuotient Cut. Em experimentoscomputacionais efetuados por Freivalds [10], seu algoritmo apresentou um consumo de tempoestimado emO(n1.6) quando o grau de cada vértice é uma constante pequena eO(n2.6) paragrafos densos. Apesar disso, não há uma prova de que sua complexidade de tempo no pior casoseja polinomial. Utilizando o resultado de Freivalds [10] podemos enunciar o seguinte teorema.

Teorema 5.3.7Há um algoritmo8 log n-aproximado para o problema UML com complexidadede tempo estimada emO(m n3.6).

Note que seI é uma instância para o problema UML, seu tamanho, denotado por size(I), éO(n(n + m)). Assim, a complexidade estimada para nosso algoritmo éO(size(I)2.3).

Se utilizarmos o algoritmoO(log n)-aproximado de Aumann e Rabani [1] para o problemaQuotient Cut, podemos substituir o teorema 5.3.8 pelo seguinte teorema.

Teorema 5.3.8Há um algoritmoO(log2 n)-aproximado para o problema UML com complex-idade de tempo polinomial.

5.4 O Fator de aproximação éΩ(log n)

Nesta seção mostraremos que o fator de aproximação do algoritmo GUL é Ω(log n) através daapresentação de uma família de instâncias, onde o fator de aproximação éΩ(Hn) quando uti-lizado o algoritmo GUL . Para tanto, assumimos queASC é um algoritmo guloso que selecionao conjunto de menor custo efetivo em cada iteração.

5.4. O Fator de aproximação éΩ(log n) 83

Dado um inteiron e valores positivosǫ1 e ǫ2, onde0 < ǫ1 ≪ ǫ2 ≪ 1/n2, definimos umainstânciaIn = (L, P, c, w) da seguinte forma:

• L = 1, . . . , n,

• P = 1, . . . , n,

• para cadai ∈ P e l ∈ L, definacil como segue

cil =

ǫ1 sei ∈ 1, . . . , n− 1 e l = i,

ǫ2 sei ∈ 1, . . . , n− 1 e l = n,

1 sei = n e l = n,

∞ demais casos,

• para cadai, j ∈ P , definawij como segue

wij =

1

n− i + 1sei ∈ 1, . . . , n− 1 e j = n,

0 caso contrário.

A instânciaIn é apresentada na figura 5.13. No próximo teorema mostraremosque o algoritmoGUL pode obter uma solução para a instânciaIn com um fator deΩ(log n) do ótimo.

1 4 n− 1

ǫ1 ǫ1

1

ǫ2 ǫ2

2 3

ǫ1 ǫ1

ǫ2

n

ǫ2 ǫ2

1n−2

1n−1

1n

12

1n−3

Figura 5.13: Uma instânciaIn.

Teorema 5.4.1Se o algoritmoGUL usa um algoritmo guloso como subrotina para o problema

de cobertura por conjuntos, entãoGUL (In)OPT(In)

→ Hn comǫ1, ǫ2 → 0, ondeOPT(In) é o valor deuma solução ótima paraIn.


Prova. A solução ótima para a instânciaIn é a estrela(n, P ) com custo1 + ǫ2(n − 1).Agora, vamos provar que a solução obtida pelo algoritmo GUL pode ser formada pelas estrelas(1, 1), (2, 2), . . . , (n, n) e custarHn + ǫ1(n− 1).

O teorema pode ser provado por indução no número de iterações.Dado uma estrelaS = (l, US), paral ∈ L e US ⊆ P , denotamos porWi(l, US) o custo

amortizado deS nai-ésima iteração, e seu valor éWi(l, US) =w′

S

|US∩U |, ondeU é o conjunto de

objetos não associados até ai-ésima iteração.Apesar do número de estrelas ser grande, podemos considerarapenas algumas estrelas,

como é mostrado no próximo fato.

Fato 5.4.2 Todas as estrelas que possuem custo limitado são da seguinteforma

• (i, i) para i = 1, . . . , n;

• (n, US) para qualquer conjuntoUS ⊆ P, US 6= ∅.

Considere a primeira iteração do algoritmo. Neste caso vamos provar que a estrela de menorcusto efetivo é a estrela(1, 1). A seguinte desigualdade é imediata:

W1(1, 1) < W1(2, 2) < . . . < W1(n, n). (5.14)

W1(i, i) < W1(n, i), para todoi ∈ 1, . . . , n− 1. (5.15)

Da desigualdade (5.14) e (5.15) podemos concluir queW1(1, 1) é menor ou igual ao custoefetivo de todas as estrelas de tamanho 1.

ComoW1(1, 1) = 1/n + ǫ1 eW1(n, P ) = 1/n + n−1n

ǫ2, temos

W1(1, 1) < W1(n, P ). (5.16)

Considere as estrelas que possuem o conjunto de objetosQ, onden ∈ Q e Q ⊆ P . Comoa adição de um objetoi ∈ P \ Q emQ diminui o custo de separação e o aumento no custo deassociação não é significativo (apenasǫ2 é acrescentado), temos

W1(n, P ) ≤W1(n, Q). (5.17)

Através da desigualdade (5.16) e (5.17) podemos concluir que qualquer estrela que contenhao objeton tem custo maior queW1(1, 1).

Agora, considere uma estrela com o conjunto de objetosQ ⊆ P \ n, Q 6= ∅. Um argu-mento minimal diz que

W1(n, i) ≤W1(n, Q), parai = minQ ∩ U. (5.18)

5.4. O Fator de aproximação éΩ(log n) 85

A desigualdade (5.18) é válida devido à

W1(n, i) = mini′∈Q∩U

1

n− i′ + 1+ ǫ2

e

W1(n, Q) ≥ averagei′∈Q∩U1

n− i′ + 1+ ǫ2.

Através das desigualdades anteriores podemos concluir quetodas as estrelas tem um custoefetivo maior queW1(1, 1). Assim, a estrela(1, 1) entra na solução obtida pelo algoritmoGUL na primeira iteração.

AtualizandoU , o conjunto de objetos não associados, podemos notar uma propriedade queé invariante. Na segunda iteração esta claro que

W2(2, 2) < W2(3, 3) < . . . < W2(n, n) (5.19)

e comoW2(2, 2) = 1/(n− 1) + ǫ1 eW2(n, P ) = 1/(n− 1) + n−1n−1

ǫ2 temos

W2(2, 2) < W2(n, P ). (5.20)

De modo similar podemos concluir que todas as estrelas tem umcusto efetivo maior queW2(2, 2) na segunda iteração. Assim, o algoritmo guloso selecionaráa estrela(2, 2) paraentrar na solução.

O posso da indução é direto. Por conseqüência, a solução produzida pelo algoritmo GUL

consiste deφ(1) = 1, φ(2) = 2, . . . , φ(n) = n.

Capítulo 6

Resultados

Neste capítulo apresentamos uma comparação teórica entre os algoritmos, analisando acomplexidade computacional dos algoritmos apresentados para o problema de classificaçãométrica uniforme. Apresentamos, também, os resultados obtidos quando estes algoritmos sãoaplicados em instâncias geradas computacionalmente e instâncias práticas.

6.1 Experimentos Computacionais

Na literatura encontramos três principais abordagens parao problema de classificação métrica,que são:

• a abordagem apresentada por Kleinberg e Tardos [17] (seção 3.1 pg.13), denotada porMKT . Desta abordagem temos dois algoritmos, um para o problema UML e um para oproblema ML, denotaremos porAK o algoritmo para o problema UML;

• a abordagem apresentada por Chekuri et al.[7], denotada porMCKNZ. Desta abordagemtemos algoritmos para os problemas ML, UML, LML e TML, denotaremos porAC oalgoritmo para o problema UML;

• a abordagem de Gupta e Tardos [11], denotada porMGT , da qual temos um algoritmopara o problema TML, que denotaremos porAGT .

As abordagens deMKT e MCKNZ são baseadas na resolução de um programa linear. OsalgoritmosAK , baseados na abordagemMKT , precisam resolver um programa linear que écomposto deO(n2m) restrições comO(n2m) variáveis, correspondendo a uma matriz comO(n4m2) elementos. Já os algoritmos baseados na abordagemMCKNZ , para uma instância dem classes en objetos, resolve um programa linear que possuiO(n2m2) restrições eO(n2m2)

variáveis, correspondendo assim a uma matriz comO(n4m4) elementos.

86

6.1. Experimentos Computacionais 87

A abordagemMGT por sua vez não utiliza programação linear e é baseada em um algoritmode fluxo em redes. O algoritmoAGT executa a cada iteração um algoritmo que busca o cortede menor capacidade em um rede de fluxos, construída sobre o conjunto de objetos e classes,contendoO(n2m) arestas. O algoritmo do corte mínimo é aplicadoO((m/M)(log Q0+log ǫ−))

vezes, para conseguir uma aproximação de(4 + ǫ)Q(f ∗) vezes o ótimo, ondeM é o valor dotruncamento da distância entre as classes eQ0 é o custo da classificação de partida, geralmenteuma classificação aleatória. Veja o capítulo 4 para maiores informações.

Implementamos os algoritmosAK , AC e o nosso algoritmo, denotado por GUL . A primeiradificuldade que observamos ao iniciar a fase de testes foi a falta de instâncias para testar osalgoritmos implementados. Tentamos entrar em contato com outros pesquisadores na busca deinstâncias reais para o problema de classificação uniforme,mas não obtivemos sucesso. Devidoà necessidade de instâncias para atestar a correção dos algoritmos e comparar seus resultados,construímos instâncias computacionalmente. Na subseção seguinte apresentamos uma análisedas instâncias utilizadas no processo.

6.1.1 As Instâncias

Em nosso algoritmo, a cada iteração, ocorre indiretamente aconstrução de uma estrela de menorcusto amortizado aproximada para todas as classes. Para simplificar a análise das instâncias,vamos considerar a construção das estrelas de menor custo amortizado ótimas.

Ao construirmos uma estrela de menor custo amortizado para uma classei com um conjuntoP den objetos, um subconjunto de objetosP ′ ⊆ P é escolhido para formar a estrela da classei. Os objetos emP ′, que formarão a estrela para a classei, são aqueles que fazem com que ovalor da equação ∑

u∈P ′ cui +∑

u 6=v:u∈P ′,v 6∈P ′ w(u, v)

|P ′|seja minimizado.

Analisando o nosso algoritmo percebemos que o tempo necessário para a obtenção de umasolução depende do número de objetos escolhidos para compora estrela em cada iteração.Assim, a maior complexidade de tempo para o algoritmo GUL ocorre quando o número deobjetos associado a cada iteração é pequeno, tendo em vista que a cada construção de umaestrela de menor custo efetivo é executado o algoritmo para oproblemaQuotient Cut, quepossui complexidade de tempo igual aO(n2,6).

A escolha dos objetos que vão compor a estrela é baseada nos seus custos de associação eseparação. O nosso objetivo é construir instâncias que demandem maior tempo de execução,para que o algoritmo GUL não seja favorecido no momento da comparação. Para construir taisinstâncias temos que escolher quais valores serão atribuídos às funções do custo de associaçãoe do custo de separação. Para que o número de objetos escolhidos a cada iteração seja pequeno,

88 Capítulo 6. Resultados

preferencialmente um, o custo de uma estrela, que contenha apenas um objetou, tem que sermenor que o custo amortizado de qualquer outra estrela que contém mais de um objeto.

O primeiro passo para obter uma estrela que seja composta porapenas um objetou é definiro custo de separação menor que o custo de associação. Considerando que o grafoG = (P, E)

é completo, ou seja, um objeto relaciona-se com todos os outros, o valor do custo de as-sociação tem que ser proporcional ao número de objetos e ao custo de separação para quecui ≥

∑v 6=u:v∈P w(u, v).

Com essa configuração o objetou é escolhido somente secui = minv∈P cvi. Como todos oscustos de associação são grandes em relação aos custos de separação, e o valor decui é o menorde todos, então um novo objetov será acrescentado à estrela somente se o custo amortizadoparau ev for menor que o custo da estrela construída somente com o objeto u. Ou seja,

cui +∑

v 6=u:v∈P

w(u, v)

1<

cui + cvi +∑

y∈P\u,v

w(y, u) +∑

y∈P\u,v

w(y, v)

2

=

2 · cui + (cvi − cui)− w(u, v) + 2∑

y 6=u:y∈P

w(u, y)

2

= cui +∑

y 6=u:y∈P

w(u, y) +(cvi − cui)− w(u, v)

2.

Para que apenas o objetou faça parte da estrela da classei, ou seja, para que a desigualdadeseja válida, o valor decvi − cui tem que ser maior quew(u, v). Baseados nisso, se definirmos ocusto de associaçãocui, para todou ∈ P e i ∈ L, igual arandom(100 · n · c), onden = |P |, c

é uma constante erandom(t) devolve um valor aleatório entre 0 et, ew(u, v) = random(c),teremos que o valor esperado de instâncias geradas que vão dar origem a estrelas com mais deum objeto é pequeno. Alguns testes computacionais mostram que este número é em torno de1%.

6.1.2 Os Testes e Seus Resultados

Implementamos o algoritmo para o problema de classificação métrica uniforme de Kleinberge Tardos [17], denotado porAK , o algoritmo apresentado por Chekuri et al. [7], denotado porAC , e o nosso algoritmo, denotado por GUL . Como visto anteriormente, os algoritmosAK eAC utilizam programação linear para obter uma solução fracionária para o problema. Nestescasos utilizamos o pacote de programação linear Xpress-MP [19]. A implementação foi feitaem linguagemC + +. Todos os testes foram executados em uma Athlon XP com 1,2 Ghz, 700MB de RAM.


Executamos cinco baterias de testes. Nas instâncias utilizadas na primeira bateria de teste, onúmerom de classes é igual à metade do númeron de objetos, ou seja,(n, m) ← (⌊2k

3⌋, ⌈k

3⌉).

Outra característica destas instâncias são os custos de associação e separação, definidos comocui ← random(1000), ∀u ∈ P, ∀i ∈ L ewe = random(10), ∀e = u, v : u, v ∈ P .

Utilizando o algoritmoAC a maior instância que conseguimos resolver tem 46 objetos e24 classes e foi preciso para isso 4 horas e 38 minutos. Não foipossível resolver instânciasmaiores que esta, devido ao tamanho muito grande do programalinear gerado. Quando apli-camos o algoritmo GUL na mesma instância, obtivemos uma solução que é 0,25% pior emapenas 7 segundos. A maior instância resolvida pelo algoritmo AK nesta bateria de testes foide 80 objetos e 40 classes com tempo de execução de aproximadamente 4 horas e 19 minutos.Quando aplicamos o algoritmo GUL na mesma instância, obtivemos um resultado 1,01% piorem 1,21 minutos.

Nesta primeira bateria de testes percebemos que a maior limitação para o uso do algoritmoAK é o tempo de execução, enquanto que para o algoritmoAC , além da restrição do tempode execução, há também limitações quanto à quantidade de memória utilizada. O tempo gastopelos algoritmosAK e AC foi basicamente para resolver o programa linear correspondente.Veja a figura 6.1 para comparar o tempo de execução de cada algoritmo.

0

2000

4000

6000

8000

10000

0 50 100 150 200 250 300 350

Tem

po (

s)

(n+m)

Gul A_k A_c

Figura 6.1: Comparação do tempo de execução dos algoritmos implementados na primeirabateria de testes.

Podemos observar na figura 6.1 que há uma redução brusca na função de tempo associada aoalgoritmo GUL quandon+m alcança 291. Como citado na subseção 6.1.1, este comportamentoocorre porque nas instâncias de tamanhon+m < 291 o número de objetos classificados a cadaiteração é baixo, devido ao custo de associação ser, para um objeto ou vários objetos, ser maiorque o custo da separação.

Analisando as instâncias utilizadas nesta bateria de testes, temos que o valor esperado docusto de associar um objeto a uma classe é 500. Já o custo esperado da relação entre os objetos


é 5. Assim, para uma instância onden + m = 291, ou seja,n = 194 e m = 97, o custoesperado de separar um objeto dos demais é5 ∗ 193 = 965 que é maior que o custo esperado deassociação para esta instância. Isto implica que o custo de classificação é minimizado quandoum grande número de objetos são associados à mesma classe em uma mesma iteração. Nestabateria de testes, quandon + m < 291 o número médio de objetos associados em cada iteraçãofoi de 1,2, e para instâncias maiores, o número médio de objetos associados em uma iteraçãofoi 32,3 o que implica na redução do número de iterações e na redução do tempo de execução.

Em uma segunda bateria de testes mantivemos a mesma proporção em relação ao número declasses com o número de objetos e alteramos a relação entre o custo de associação e separação,onde definimos o custo de associaçãocui, para todou ∈ P e i ∈ L, igual arandom(5 ·n), onden = |P |, ew(u, v) = random(5 ). Nestas instâncias não tivemos uma queda brusca no tempode execução do algoritmo GUL , como ocorreu nas instâncias anteriores, devido ao custo deassociação se manter proporcional ao número de objetos e o custo de separação ser constante.

Para essa bateria de testes a maior instância que conseguimos resolver, utilizando o algo-ritmo AC , possuía 46 objetos e 24 classes, e foram precisos para isso 5horas e 12 minutos.Não foi possível resolver instâncias maiores que esta, devido ao tamanho do programa lineargerado ultrapassar 1 Gb de memória. Quando aplicamos o algoritmo GUL na mesma instância,obtivemos uma solução que é 1,25% pior em apenas 7 segundos. Amaior instância resolvidapelo algoritmoAK foi de 120 objetos e 65 classes e o tempo necessário para sua resolução foide 12 horas e 20 minutos. Quando aplicamos o algoritmo GUL na mesma instância, obtivemosum resultado 0,48% pior em 1,08 minutos. A maior taxa de erro obtida pelo algoritmo GUL

em relação aoAK nessa bateria de testes foi de 11,53%, e em todas as instâncias dessa bateriade testes, quando aplicado o algoritmo GUL , havia um número pequeno de objetos associadosem cada iteração. Na média 1,03 objetos associados a cada iteração. Veja a figura 6.2 com ográfico de comparação dos resultados obtidos.

Em uma terceira bateria de testes buscamos variações na relação entre o número de objetose o número de classes, fixandon oum e variando o outro. Nesta fase dos testes não utilizamoso algoritmoAC por este possuir alto custo computacional, e as suas soluções serem iguais àssoluções apresentadas pelo algoritmoAK . Os resultados estão apresentados na tabela 6.1. Acoluna Erro(%) corresponde ao valor de(GUL(I)/AK(I) − 1) · 100, para cada instânciaI.A maior taxa de erro obtida neste caso é de 1,25% e, como esperado, o ganho de tempo éconsiderável quando fixamos o número de classes e aumentamoso número de objetos.

Podemos observar nos resultados da terceira bateria de testes, ilustrados na tabela 6.1, que oalgoritmoAK teve um acréscimo mais significativo no seu tempo de execuçãoquando fixamoso número de classes e aumentamos o número de objetos. Este comportamento já era esperado,tendo em vista que o tempo do algoritmoAK é baseado na resolução de um programa linearcomO(n2m) restrições eO(n2m) variáveis. O mesmo ocorre com o algoritmo GUL mas emuma escala menor, pelo fato de que a complexidade do algoritmo GUL éO(m n3,6) para grafos


0

5000

10000

15000

20000

25000

30000

35000

40000

45000

0 50 100 150 200 250 300 350

Tem

po (

s)

(n+m)

Desempenho dos Programas

GulA_KA_c

Figura 6.2: Comparação do tempo experimental dos algoritmos implementados.

densos.

Uma outra bateria de testes foi executada sobre instâncias com número fixo de objetos e declasses, 40 objetos e 20 classes, e variando a relação entre ocusto de associação e o custo deseparação. O custo de associação é dado porcui ← random(1000), e o custo de separação édado porw(u, v)← random(10ρ), ondeρ é um valor inteiro e varia de 1 até 100. Os resultadospodem ser visto na tabela 6.2.

Visto que o custo de separação aumenta quandoρ aumenta, grandes estrelas se tornampromissorras para fazer parte da solução. Quando grandes estrelas entram na solução, o númerode iterações decresce. Note que a instância mais difícil ocorre na transição entre grandes estrelase pequenas estrelas. Quando o custo de separação é grande (ρ > 80), o problema se torna fácil,já que o objetivo se torna conectar todos os objetos em uma classe. Quandoρ = 80 a instânciacorrespondente é “difícil” para o algoritmo GUL , já que o fator de aproximação aumenta, estainstância também é “difícil” para o algoritmoAK , já que o tempo de execução também aumenta.Deste experimentos podemos concluir que a razão entre o custo de associação e separação é umacaracterística importante em instâncias difíceis.

Observamos que menos de 1% das instâncias utilizadas até o momento da execução destabateria de testes tinham gerado soluções fracionárias paraos programas lineares (KT), de Klein-berg e Tardos [17], e (CKNZ), de Chekuriet al. [7]. Nesta última bateria de testes surgiramalgumas instâncias que geraram soluções fracionárias paraos programas lineares, e após ana-lisarmos estas instâncias conseguimos identificar características que nos levaram a uma novabateria de testes, onde cerca de 10% das instâncias geradas resultaram em soluções fracionáriaspara os programas lineares. Como características destas instâncias temos que o tamanho doconjunto de objetos é igual a 40, o número de classes é igual a 20, a relaçãowuv entre os ob-


jetos é igual arandom(8) e o custo de associação é igual arandom(192) ou random(200) ourandom(208).

O maior erro entre o valor devolvido pelo algoritmoAK e a solução do programa linear(KT), para as instâncias com as características apresentadas anteriormente, foi de 24,17% eforam necessários 17 minutos para obter a solução neste caso, enquanto que o erro para oalgoritmo GUL para esta mesma instância foi de 7,15% usando apenas 4 segundos. O erromédio das instâncias cujo valor da solução do programa linear é fracionária é de 7,02% comum tempo de execução médio de 16,93 minutos, enquanto que o erro médio para o algoritmoGUL quando aplicado nas mesmas instâncias é de 5,8% com tempo de execução médio de 3,02segundos.

Para todas as instâncias utilizadas nos testes anteriores ografoG = (P, E) é completo, ouseja, cada objeto se relaciona com todos os outros. Baseadosnas características das instânciasda última bateria de testes, geramos instâncias onde o grafoG = (P, E) é um grafo não muitodenso, com grau médio dos vértices igual a 2. Mais precisamente, estas novas instâncias sãoformadas por 20 objetos e 10 classes, com em média 40 arestas entre os objetos, custo deassociação é igual arandom(20) e o custo de separação é igual arandom(8). Cerca de 8% dasinstâncias com estas características geravam resultados fracionários para os programas linearese o maior erro para o algoritmoAK em relação à solução fracionária do programa linear foi de21,34% com erro médio de 6,47%, enquanto que o maior erro parao algoritmo GUL , quandocomparado com a solução fracionária do programa linear, é de50,89% e com erro médio de13,46%.

Os resultados computacionais que obtivemos com estas instâncias nos forneceu maior co-nhecimento para gerar instâncias difíceis. Isto nos conduziu às instânciasIn que provam que oalgoritmo GUL possui um fator de aproximação deΩ(log n) (veja a seção 5.4).

Para ilustrar a aplicabilidade do algoritmo primal-dual eminstâncias práticas, aplicamos oalgoritmo ao problema de recuperação de imagens, com uma imagem degenerada por ruídos.A imagem possui uma malha de pontos em tons de cinza e dimensões 60x60, com um total de3600 pontos (objetos) para serem classificados nas cores branco ou preto. Para definir o custode associação e separação consideramos que cada cor é um inteiro entre 0 e 255. O custo deassociação de um objetou a uma classei é dado porcui = |clr(u)− clr(i)|, ondeclr(u) é a coratual do pontou e clr(i) é a cor associada à classei. O custo de separação de um objetou eum objetov é dado porwuv = 255− |clr(u)− clr(v)|. Nestas imagens consideramos apenas osoito vizinhos mais próximos de cada ponto.

As seguintes imagens, apresentadas nas figuras 6.3–6.6, apresentam o resultado obtido apli-cando o algoritmo primal-dual. Em cada figura, a imagem da esquerda foi obtida inserindoalguns ruídos e a imagem da direita é a imagem obtida após a classificação dos objetos.

A diferença de tempo de classificação entre as imagens ocorreporque o custo de separaçãonas imagens com menos ruído é maior que em imagens com mais ruído, fazendo com que o


Figura 6.3: Imagem com 25% de ruído.Tempo necessário de 4,8 minutos.




número de objetos classificados a cada iteração seja maior.Apesar destes tempos serem altos para aplicações de processamento de imagens, eles servem

para ilustrar a aplicabilidade e a qualidade das soluções donosso algoritmo. Além disso, eminstâncias reais, possivelmente grandes, é possível trabalhar com o sistema de janelas, onde aimagem é dividida em partes menores e então é aplicado o algoritmo de classificação, fazendocom que o tempo de execução seja menor. Claramente, o problema de classificação métricaé mais geral que o problema de restauração de imagens e o algoritmo primal-dual se mostraapropriado para instâncias de tamanho moderado e grande.


Instância Tempo (s)Objetos (n) Classes (m) GUL AK Erro (%)40 5 0 1 0.1840 10 2 3 0.2340 15 3 6 0.6740 20 4 9 0.2940 25 5 12 0.4740 30 5 23 0.1940 35 6 30 0.6640 40 7 36 0.2740 45 8 49 1.2540 50 9 56 0.7840 55 10 75 0.7740 60 11 94 0.4440 65 11 68 0.37

5 40 0 1 010 40 1 0 015 40 0 1 020 40 1 2 0.8725 40 2 3 0.8330 40 3 7 0.4635 40 4 17 0.7045 40 11 77 0.6250 40 16 131 0.5655 40 22 400 0.3860 40 26 912 0.4765 40 33 2198 0.60

Tabela 6.1: Tempos e soluções para os algoritmosAK e GUL com variações no número deobjetos e classes.


Tempo (s) Número deGUL AK Erro (%) ρ iterações

3 5 0.34 1 364 7 0.39 5 374 7 0.57 10 384 11 0.75 15 394 11 0.43 20 383 25 0.66 25 363 21 0.47 30 374 23 0.51 35 383 35 0.51 40 374 41 0.88 45 364 67 0.68 50 364 114 1.06 55 364 168 1.75 60 364 203 1.26 65 324 439 2.26 70 324 831 4.32 75 294 1182 13.33 80 232 790 0 85 10 549 0 90 10 262 0 95 10 114 0 100 1

Tabela 6.2: Tempos e soluções para os algoritmosAK e GUL com variações na relação entre ocusto de associação e o custo de separação.

Capítulo 7

Considerações Finais

Após estudos que culminaram nesta dissertação, verificamosque os problemas de clas-sificação métrica ainda merecem mais atenção da comunidade científica. Os algoritmos deaproximação existentes ainda apresentam complexidade de tempo alta, fazendo com que suaaplicabilidade seja restrita, como é o caso dos algoritmos que têm como passo inicial a reso-lução de um programa linear grande. Motivados pelo alto custo computacional dos algoritmospresentes na literatura e através do estudo de problemas correlatos, como o problema de locali-zação de recursos e o problema de cobertura por conjuntos, desenvolvemos um novo algoritmopara o problema de classificação uniforme.

Após finalizarmos a fase de implementação dos algoritmos, começamos a busca por ins-tâncias reais para o problema, mas não obtivemos sucesso. A solução encontrada foi gerarinstâncias computacionalmente e também oriundas do problema de recuperação de imagensdegeneradas por ruídos. Utilizando as instâncias geradas computacionalmente comparamosos resultados do nosso algoritmo com os resultados dos algoritmos baseados em programaçãolinear.

Apesar do novo algoritmo poder ser implementado em tempo polinomial com fator de apro-ximação deO(log2 n), optamos por implementar uma versão, que dá um fator de aproximaçãode 8 log n, mas não possui complexidade de tempo comprovadamente polinomial. Por outrolado ele se mostrou rápido e apresentou bons resultados quando comparado com os algoritmosbaseados em programação linear. A qualidade das soluções obtidas, apesar da análise apontarum algoritmo8 log n-aproximado, são boas, tendo uma taxa de erro média inferiora 14% dasolução ótima e o maior erro encontrado foi de 50.89% em relação ao ótimo fracionário do pro-grama linear. Por ter tempo de execução menor e usar menos memória, o novo algoritmo obtémsoluções para instâncias de tamanho moderado e grande, enquanto que os algoritmos baseadosem programação linear resolvem apenas instâncias de pequeno porte.

Sabemos que as instâncias utilizadas nos testes não refletema realidade mas elas servirampara o nosso propósito de comparar a eficácia do nosso algoritmo em relação aos demais.

96

7.1. Trabalhos Futuros 97

7.1 Trabalhos Futuros

Apresentamos a seguir alguns pontos de pesquisas que consideramos promissores:

• Estudar a aplicação da técnica de programação semidefinida ao problema de classificaçãométrica.

• Buscar instâncias práticas e interessantes para o problema, para que possamos analisarmelhor o funcionamento do algoritmo em instâncias reais.

• Continuar na busca por um algoritmo primal-dual para o problema de classificação queapresente um fator de aproximação melhor queO(logn).

• Acrescentar um custo de utilização para cada classe, que deverá ser pago quando, pelomenos, um dos objetos for associado àquela classe. Observe que com esta alteraçãotemos um problema muito semelhante ao problema de localização de recursos, com umanova restrição que dois clientes fortemente relacionados devem ser atendidos pelo mesmorecurso.

• Acrescentar a característica de que a relação entre os objetos obedeça alguma métricamais restrita. Talvez com esta característica o problema declassificação métrica possaser resolvido mais facilmente através de alguma técnica queleve em consideração estainformação.

Referências Bibliográficas

[1] Y. Aumann and Y. Rabani. AnO(log k) approximate min-cut max-flow theorem andapproximation algorithm.SIAM Journal on Computing, 27(1):291–301, 1998.

[2] Y. Bartal. Probabilistic approximations of metric spaces and its algorithmic applications.In IEEE Symposium on Foundations of Computer Science, pages 184–193, 1996.

[3] Y. Bartal. On approximating arbitrary metrics by tree metrics. InProceedings of the 30thAnnuall ACM Symposium on Theory of Computing, pages 161–168, 1998.

[4] Yuri Boykov, Olga Veksler, and Ramin Zabih. Markov random fields with efficient ap-proximations. Number TR97-1658, page 10. IEEE Conference on Computer Vision andPattern Recognition, 3 1997.

[5] M.H. Carvalho, M.R. Cerioli, R. Dahab, P. Feofiloff, C.G.Fernandes, C.E. Ferreira, K.S.Guimarães, F.K. Miyazawa, J.C. Pina Jr., J. Soares, and Y. Wakabayashi.Uma introduçãosucinta a algoritmos de aproximação. Editora do IMPA - Instituto de Matemática Purae Aplicada, Rio de Janeiro–RJ, 2001. M.R. Cerioli, P. Feofiloff, C.G. Fernandes, F.K.Miyazawa (editors).

[6] M. Charikar, C. Chekuri, A. Goel, and S. Guha. Rounding via trees: deterministic ap-proximation algorithms for group steiner trees andk-median. InProceedings of the 30thAnnual ACM Symposium on Theory of Computing, pages 114–123, 1998.

[7] C. Chekuri, S. Khanna, J. Naor, and L. Zosin. Approximation algorithms for the metriclabeling problem via a new linear programming formulation.In Proceedings of the ACMSymposium on Discrete Algorithms, pages 109–118, 2001.

[8] V. Chvátal. A greedy heuristic for the set-covering problem.Math. of Oper. Res., 4(3):233–235, 1979.

[9] J. Fakcheroenphol, S. Rao, and K. Talwar. A tight bound onapproximating arbitrarymetrics by tree metrics. InProceedings of the 35th Annual ACM Symposium on Theory ofComputing, pages 448–455, 2003.

98

REFERÊNCIAS BIBLIOGRÁFICAS 99

[10] K. Freivalds. A nondifferentiable optimization approach to ratio-cut partitioning. InProc. 2nd Workshop on Efficient and Experimental Algorithms, number 2647 in LecturesNotes on Computer Science. Springer, Verlag, 2003.

[11] A. Gupta and E. Tardos. Constant factor approximation algorithms for a class of classifi-cation problems. InProceedings of the 32nd Annual ACM Symposium on the Theory ofComputing, pages 125–131, 1998.

[12] D.S. Hochbaum, editor.Approximation Algorithms for NP-Hard Problems. PWS Publish-ing Company, 1997.

[13] H. Ishikawa and D. Geiger. Segmentation by grouping junctions. InProceeding of IEEEConference on Computer Vision and Pattern Recognition, pages 125–131, 1998.

[14] K. Jain, M. Mahdian, E. Markakis, A. Saberi, and V. Vazirani. Greedy facility location al-gorithms analyzed using dual fitting with factor-revealinglp. Journal of ACM, 50(6):795–824, 2003.

[15] K. Jain and V.V. Vazirani. Primal-dual approximation algorithms for metric facility loca-tion and k-median problems.Journal of the ACM, Vol. 48, pages 274–296, 2001.

[16] L. Kaufman and P.J. Rousseeuw.Finding Groups in Data: An Introduction to ClusterAnalysis. John Wiley & Sons, 1990.

[17] J. Kleinberg and E. Tardos. Approximation algorithms for classification problems withpairwise relationships: Metric labeling and markov randomfields. InProceedings of the40th Annuall IEEE Symposium on Foundations of Computer Science, pages 14–23, 1999.

[18] T. Leighton and S. Rao. Multicommodity max-flow min-cuttheorems and their use indesigning approximation algorithms.Journal of the ACM, 46 , No. 6:787–832, Nov. 1999.

[19] Dash Optimization.Xpress-MP Manual. Release 13. 2002.

[20] S. Peleg, M. Werman, and H. Rom. A unified approach to the change of resolution:space and gray-level. InIEEE Transactions on Pattern Analysis and Machine Intelligence,number 11, pages 739–742, 1989.

[21] Y. Rubner, C. Tomasi, and L. Guibas. The earth mover’s distance as a metric for imageretrieval. International Journal of Computer Vision, 40(2):99–121, 2000.

[22] V. Vazirani. Approximation Algorithms. Springer-Verlag, 2000.

100 REFERÊNCIAS BIBLIOGRÁFICAS

[23] D.P. Williamson. Lecture notes on approximation algorithms. Technical Report RC 21409,T.J. Watson Research Center (IBM Research Division), Yorktown Heights, New York,1998.

Documents

Algoritmos de Aproximação para o Problema de Classiﬁcação ...evandro/tese.pdf · sentamos um algoritmo 8logn-aproximado, analisado pela técnica primal-dual, que apesar de