Final Brasileira da Maratona de Programação 2010

Outubro 29, 2010

Nos dias 22 e 23 aconteceu a final brasileira da maratona de programação, em Joinville, SC, organizada pela Universidade do Estado de Santa Catarina, UDESC.

22 de Outubro

Infelizmente, só conseguimos o financiamento para ônibus, que leva cerca de 10h entre Campinas e Joinville. Saímos às 19h de Campinas na Quinta-feira, dia 21 e chegamos às 5 da manhã de Sexta-feira em Joinville. Como a reserva era para o dia 22, teríamos que esperar até 12h para fazer o check-in. No final das contas, só conseguimos entrar nos quartos às 14h, bem na hora do warm-up! Foi meio corrido e cansativo, mas deu tudo certo.

Logo depois, assistimos a uma palestra da IBM, seguida de uma reunião só com os coaches. Aí fomos passear de barco na Baía de Babitonga. Saímos de Joinville e fomos até São Francisco do Sul, onde a janta foi servida no próprio barco (felizmente ninguém do nosso time enjoou) e depois regressamos. O passeio durou umas 4 horas.

Barco “Príncipe de Joinville”, no Píer

23 de Outubro

Para descansar o máximo possível, os competidores optaram por dormir até mais tarde no Sábado, pulando o café da manhã. Logo após o almoço começou a competição e devo adiantar que o nervosismo que a gente passa como técnico é maior do que como competidor!

A mesma prova é aplicada em várias sedes da América Latina, mas em algumas o horário de início é diferente. Nós técnicos não tivemos acesso ao placar até que todas as sedes já tivessem iniciado, pois, como tínhamos acesso à internet, divulgar o placar online serviria de dica dos problemas mais fáceis para as sedes que ainda não tivessem começado. Assim, só ficamos sabendo a classificação depois de duas horas.

Qual não foi minha surpresa ao ver que o time Alfa da Unicamp estava com apenas 3 problemas e em 20° lugar, enquanto tinha equipes já com 6 problemas. Essa minha angústia perdurou um pouco mais, até que de repente, eles resolveram 4 problemas em menos de 10 minutos! Nessa hora eles pularam para sexto lugar. Infelizmente, devido à alta penalidade (em decorrência da submissão tardia desses 4 problemas), dois outros times fizeram 7 problemas e os ultrapassaram, colocando-os em oitavo lugar. Nesse momento o placar congelou. Como não estávamos vendo os competidores para saber se mais balões chegavam, tivemos que esperar até a cerimônia de encerramento para saber a classificação final.

Times durante a competição

A cerimônia foi logo depois da competição. Em anos anteriores, utilizava-se um programinha para mostrar a evolução do placar no período em que ficou congelado, mas o autor do software e o único que sabia como operá-lo era o Fábio Dias que não pôde comparecer ao evento. Assim, a organização do evento foi mostrando o log de submissões dos últimos minutos e descobrimos que a Poli-USP também tinha passado à nossa frente. No final ficamos com a nona posição e ganhamos a medalha de bronze. O placar final pode ser acessado aqui.

O time “Garotos da OBI” era formado pelo Caíque, Felipe e Renato, 3 dos 4 alunos classificados na seletiva para a IOI esse ano, sobre a qual escrevi num outro post (o André estava no time da Poli-USP). Eles participaram como convidados da maratona e portanto não são classificáveis para a final mundial. Embora estejam ainda no ensino médio, podemos ver que o nível deles já é equivalente ao das melhores equipes. Isso é um sinal de que a olimpíada de informática está se fortalecendo, o que é essencial para a formação de equipes competitivas a nível mundial. Quem sabe daqui a alguns anos veremos algum time brasileiro ganhando medalhas na final mundial.

O Unicamp Beta não ficou muito bem classificado, tendo feito apenas dois problemas. Eles ficaram meio chateados, mas falei para eles considerarem o grande feito que já tinham realizado ao conseguir a vaga para a final nacional. Lembrando que o Alex está apenas no segundo ano e o Igor e a Patrícia aprenderam a programar esse ano! Se continuarem se dedicando, eles estarão no primeiro time da Unicamp daqui a alguns anos e nos classificarão para um próximo mundial.

Apesar de o desempenho da nossa equipe não ter sido um dos melhores, ainda há esperança quanto ao mundial. Levando em conta que o “Garotos da OBI” não são elegíveis e que o segundo time do ITA não pode ir à final (a regra permite no máximo um por universidade), estamos em sétimo na lista de espera por uma vaga. Parece pouco promissor, mas ano passado tivemos exatas 7 vagas para o mundial em Harbin, embora essa quantidade mude todo ano. Agora só resta torcer e, para os que ainda podem competir, voltar a treinar o quanto antes.

24 de Outubro

Aproveitando que nosso ônibus era só para as 22h, fomos conhecer um pouco a cidade de Joinville. Só conseguimos visitar os museus da Imigração e do Sambaquis, além do parque zoobotânico, todos de entrada franca. Infelizmente um dos principais cartões-postais da cidade, o mirante, estava interditado. Além disso, um dos museus que eu mais queria ver, o museu da bicicleta, foi fechado! O museu tinha sido aberto em comemoração aos 150 anos de Joinville — que é conhecida como a cidade das bicicletas — e expunha uma grande coleção de bicicletas de um acervo particular. A prefeitura pagava o aluguel do espaço e o dono das bicicletas ficava como curador do museu. Com a mudança de mandato na prefeitura, perdeu-se o interesse em manter o museu e o desabamento do telhado do prédio ababou decretando o fechamento do local.

Moedor de cana-de-açúcar (Museu dos Imigrantes)

Podíamos ainda visitar o parque de exposições Expoville, mas já estava meio tarde e o local ficava um pouco longe. Preferimos ir jantar em um shopping, onde o Paulo perdeu a passagem de volta dele >.< No final ele teve que comprar outra, mas felizmente pôde embarcar de volta conosco.

Conclusão

Gostei de ser técnico, mas não poderei continuar sendo ano que vem. Além disso, não está nos meus planos continuar os treinos esse ano (principalmente porque pouca gente se interessaria) e não sei se vou me envolver com treinamentos ano que vem. Ainda não temos um substituto concreto para o cargo, mas cogita-se professores.

Anúncios

Desigualdades Definidoras de Facetas

Outubro 22, 2010

No último post da série sobre combinatória poliédrica, apresentei o algoritmo de Branch and Cut. Um aspecto essencial no desempenho desse algoritmo é o quanto uma desigualdade é capaz de aproximar uma formulação da envoltória convexa. Vimos que as desigualdades definidoras de facetas são as mais eficientes na prática.

Hoje vou discutir um pouco sobre métodos para determinar se uma dada desigualdade define faceta para a envoltória convexa. Para tal, precisamos revisar alguns conceitos de álgebra linear.

Álgebra Linear

Independência linear: o conjunto de vetores  é linearmente independente se

(1)

então, para todo i = 1, …, n

Para . Em outras palavras, não existe um vetor que possa ser escrito como combinação linear de outro.

Independência (linear) afim: o conjunto de vetores  é afim independente se

(2)

e (3)

então, para todo i = 1, …, n

Para . Aqui temos a restrição adicional de que a soma dos coeficientes deve ser 0. Observe que se o vetor nulo estiver no conjunto de vetores, esse nunca será linearmente independente, pois se a igualdade em (1) valesse, qualquer coeficiente não-nulo multiplicando o vetor nulo manteria a igualdade. Porém, a adição da desigualdade (3), garante nesse caso que o coeficiente do vetor nulo seja 0. Essa notação é interessante para não termos que tratar o vetor nulo como um caso especial ao fazer algumas contas.

Vamos apresentar a seguir dois possíveis métodos que podem ser utilizados para decidir se uma dada desigualdade define faceta de um poliedro.

Método Direto

Existe um teorema que diz que a dimensão de um poliedro é igual ao maior número de pontos afim independentes pertencentes a ele, menos um. Assim, se encontramos k soluções afim independentes do nosso problema, sabemos que ele tem dimensão maior ou igual a k-1. Se o modelo tem n variáveis e o poliedro tem dimensão n, dizemos que ele possui dimensão cheia. É muito mais difícil trabalhar com poliedros de dimensão menor que n, portanto, para fins de explicação, vamos assumir daqui pra frente que o poliedro tem dimensão cheia.

Uma face qualquer de um poliedro, é também um poliedro, só que com dimensão menor. Logo, para determinar a dimensão de uma face basta enumerar pontos afim independentes que pertençam a essa face.

Como vimos, a dimensão da faceta é uma a menos do que a dimensão do poliedro. Para determinar se uma desigualdade define faceta, precisamos calcular a dimensão da insterseção da mesma com o poliedro. Para isso, devemos encontrar pontos do poliedro, que satisfaçam essa desigualdade na igualdade e que ainda sejam afim independentes entre si. Se a dimensão dessa interseção for uma a menos do que a do poliedro, tal desigualdade define uma faceta do poliedro.

Método Indireto

Encontrar pontos afim independentes pode não ser uma tarefa simples. Uma alternativa consiste em usar um método indireto.

Dada uma desigualdade válida da forma , queremos decidir se a mesma define uma faceta do poliedro P. Considere a interseção dessa desigualdade com o poliedro P, representada por . Considere os pontos x em P que satisfazem e portanto satisfazem .

Cada uma dessas igualdades formará uma linha de um sistema linear onde as variáveis são os coeficientes . Se esse sistema tiver solução única, pode-se mostrar que a desigualdade define uma faceta e que é equivalente a , ou seja .

O método indireto procura resolver esse sistema linear por partes, escolhendo pontos de P que satisfazem (e por consequência ) com o objetivo de mostrar que os coeficientes são iguais a . Se formos capazes de definir todos os coeficientes a partir desses pontos, a desigualdade define uma faceta de P. A conveniência é que não precisamos determinar se os pontos são afim independentes, pois isso é considerado implicitamente ao resolvermos o sistema linear. Além disso, como sabemos o valor esperado para os coeficientes , fica mais fácil procurar pontos que levem a essa conclusão.

Os pontos p e q definem a reta . O ponto s sozinho não consegue definir unicamente a reta .

A intuição geométrica do método pode ser vista na figura acima. Os pontos da interseção de com P são ‘p’ e ‘r’. Como a única reta (solução única) que passa por esses dois pontos é , a equação da interseção é equivalente a . Essa interseção é uma faceta de P. Já para a reta , o único ponto de sua interseção com P é o ponto s. Observe que existem infinitas retas que podem passar por ‘s’, como por exemplo a própria , mas também . Ou seja, o sistema linear correspondente não tem solução única e como podemos ver, a interseção não é uma faceta de P.

Exemplo

Para dar um exemplo do método indireto, vou usar o problema do conjunto independente. Dado um grafo não direcionado, queremos encontrar o maior conjunto de vértices de forma que nenhum deles seja vizinho entre si. Para isso, definimos uma variável binária  que vale 1 se o vértice v está no conjunto independente e 0 caso contrário. O modelo é bem simples,

(4) 

(5) 


Grafo com conjunto independente máximo marcado em laranja.

Esse modelo é bem fraco, no sentido de que na prática o valor da relaxação linear está bem distante da solução inteira ótima (poucas podas no Branch and Bound). Uma desigualdade bastante eficaz é a da clique maximal. Seja M uma clique maximal, ou seja, um conjunto de vértices tal que todos são adjacentes entre si e tal que não exista outro vértice fora de M, vizinho a todos os vértices de M. Considere a seguinte desigualdade

(6)

Ela é válida para nosso problema pois nenhum conjunto independente pode conter mais de um vértice de qualquer clique. Vamos verificar se ela define uma faceta. Suponha então que a interseção de (6) com a envoltória convexa do problema do conjunto independente seja da forma

(7)

A ideia é encontrar pontos válidos para o problema e que satisfaçam (6) na igualdade, pois assim sabemos que esses pontos satisfazem (7). Vamos chamar de o coeficiente de associado ao vértice v.

Dado um v na clique M, podemos fazer e o resto 0, que ele será um conjunto independente válido e satisfaz (6) na igualdade. Substituindo esse x em (7), temos que

(8)

Agora, dado um vértice u fora de M, temos a propriedade de que existe algum vértice em M não adjacente a u (do contrário poderíamos incluir u em M e esta não seria maximal, uma contradição). Seja então v* tal vértice em M. O ponto x, com e o resto 0, é um conjunto independente válido uma vez que u e v* não são adjacentes. Como este ponto satisfaz (7) na igualdade, temos que . Mas, por (8), chegamos que

(9)

Substituindo por pela igualdade (8), temos que cada coeficiente da desigualdade (7) é igual ao coeficiente da desigualdade (6) multiplicado por , concluindo que (7) define uma faceta.

Dá para substituir as desigualdades (5) do modelo por desigualdade (6), desde que todas as arestas (u, v) estejam na desigualdade de pelo menos uma clique maximal. Felizmente, existe um algoritmo polinomial para encontrar uma cobertura de arestas por cliques maximais [2].

Exemplo de uma cobertura por cliques maximais (arestas podem ser cobertas por mais de uma clique).

Referências

[1] Disciplina de Programação linear inteira com o prof. Cid.
[2] Nemhauser, G.L. and Sigismondi, G.A – Strong cutting plane/branch-and-bound algorithm for node packing


Algoritmo de Branch and Cut

Outubro 15, 2010

Esse é o primeiro post de uma série sobre combinatória poliédrica. Ela consiste no estudo da estrutura de problemas combinatórios e representa uma ferramenta importante na construção de modelos eficientes de progração linear inteira. Aqui vou falar sobre o algoritmo de Branch and Cut. Estou assumindo conhecimento prévio sobre Branch and Bound.

Abordagem Geométrica

Podemos pensar em programas lineares de forma geométrica. Para exemplificar, considere um programa linear de minimização (daqui pra frente, estarei sempre me referindo a esse tipo de PL), com duas variáveis (). Uma desigualdade da forma

representa um semi-plano. Em um programa linear, temos um conjunto de desigualdades que devem ser satisfeitas ao mesmo tempo. Geometricamente, isso equivale à interseção dos semi-planos. Um semi-plano é um polígono convexo (ilimitado) e a interseção de polígonos convexos é sempre um polígono convexo. Assim, o espaço de soluções é representado por um polígono convexo, ou para dimensões maiores, poliedros convexos.

Além disso, a função objetivo é da forma

Variando o valor de z, vemos que essa equação representa uma família de retas paralelas, e nosso objetivo é encontrar a reta para a qual z que seja mínimo (seja z* o z mínimo). Para dimensões maiores, a função objetivo é um hiperplano. A solução ótima (seja ela ) é um ponto do poliedro que satisfaz . É possível mostrar que a solução ótima de um programa linear está em um vértice do poliedro.


Poliedro representando a formulação de um problema com duas variáveis. As retas paralelas representam a função objetivo.

Para um programa linear inteiro, temos a restrição de que as variáveis são inteiras. Considere o conjunto P de pontos de coordenadas inteiras que são viáveis para nosso problema. Definimos a envoltória convexa como o menor polígono que contém P.

Na figura abaixo, os pontos inteiros que representam soluções viáveis para nosso problema, estão marcados em vermelho. A envoltória convexa é o polígono de borda preta. Já os polígonos em verde e vermelho são formulações válidas para nosso problema. Uma formulação é válida se não deixa nenhum ponto viável de fora e não inclui nenhum ponto inteiro que não seja viável. De fato, as duas formulações abaixo são válidas, uma vez que não deixam nenhum ponto vermelho de fora e não incluem nenhum ponto branco. Observe que existem infinitas possíveis formulações válidas para um problema.

A envoltória convexa e formulações válidas.

Para problemas NP-difíceis, não podemos encontrar todas as desigualdades que definem a envoltória convexa em tempo polinomial a menos que P=NP, já que do contrário poderíamos resolver o modelo como um programa linear (sem as restrições de integralidade) em tempo polinomial.

Entretanto, só o fato de aproximar a formulação da envoltória convexa já é interessante para o algoritmo de Branch and Bound. Lembrando que em cada nó é resolvida a relaxação linear do modelo, ou seja, remover suas restrições de integralidade. O valor obtido, chamado limitante dual, é usado para realizar podas por limitantes na árvore. A poda por limitantes funciona assim: se a relaxação for maior ou igual à melhor solução conhecida até agora, então não precisamos explorar sua subárvore, uma vez que o limitante dual é sempre menor ou igual ao valor de qualquer solução obtida nessa subárvore.

Aproximar a formulação da envoltória, tende a aumentar o valor da relaxação linear nos nós, que por sua vez tende a aumentar o número de podas por limitantes, melhorando o desempenho do algoritmo. Para isso precisamos encontrar desigualdades válidas e que aproximem o modelo da envoltória convexa. Porém, o número  de dessas desigualdades pode ser muito grande, tornando a resolução da relaxação linear muito lenta, sem contar que algumas das desigualdades podem ser irrelevantes para diminuir o valor do limitante dual. A ideia então é adicionar tais desigualdades apenas por demanda, através de algoritmos de plano de corte.

Algoritmo de Planos de Corte

Como pode ser visto na figura abaixo, o ponto ótimo da relaxação linear (azul) do polígono verde, não possui coordenadas inteiras. Assim, não é uma solução válida para o problema. A ideia é utilizar retas que “cortem” o ponto fora. Essa reta (ou hiperplano em dimensões maiores), chamada de plano de corte, nada mais é do que uma desigualdade que é satisfeita por todos os pontos viáveis (vermelhos) e não é satisfeita pelo ponto que queremos remover (azul). Às vezes, decidir se uma desigualdade representa um plano de corte é NP-difícil! Na prática, usam-se heurísticas.

Plano de corte remove a solução ótima

O que se faz em geral é encontrar famílias de desigualdades válidas a priori e, ao resolver a relaxação linear em cada nó do Branch and Bound, verificamos se a solução ótima encontrada viola alguma dessas desigualdades. Em caso positivo, inserimos a nova restrição no modelo e resolvemos a relaxação linear novamente, repetindo o processo enquanto conseguirmos melhor o limitante dual. Ao mudar de nó no algoritmo, descartamos os planos de corte adicionados.

Um corte pode não ser muito eficaz, porém. Se a desigualdade remover apenas a solução ótima, não ajudou muito a aproximar a formulação da envoltória convexa. Dado um plano de corte, ele pode ser classificado de acordo com a dimensão da sua interseção com a envoltória convexa. Na figura abaixo, vemos os três tipos de desigualdades para duas dimensões: a interseção de l1 com a envoltória é nula e tem dimensão -1; l2 com a envoltória é um ponto e tem dimensão 0; e l3 com a envoltória forma uma reta, com dimensão 1.

Possíveis planos de corte

É intuitivo pensar que os cortes mais eficazes são aqueles de dimensão maior (no exemplo, a reta l3). A prática também mostra que tais cortes são melhores. Assim, sendo n a dimensão da envoltória convexa, estamos interessados em encontrar desigualdades cuja interseção com a envoltória tenham dimensão n-1, que são justamente aquelas desigualdades que definem facetas dessa envoltória.

O Branch and Bound onde aplicamos algoritmos de plano de corte é chamado de Branch and Cut. No próximo post da série falarei sobre como determinar se uma desigualdade representa uma faceta da envoltória convexa.

Leituras adicionais e referências

[1] Disciplina de Programação linear inteira com o prof. Cid.
[2] Wolsey, L. – Integer Programming [link]


MPI – Trocas de mensagens

Outubro 8, 2010

Nesse post vou comentar sobre alguns aspectos de comunicação entre nós, através da biblioteca MPI, a qual introduzi neste outro post.

Comunicação ponto a ponto

Como diz o próprio nome, a biblioteca MPI (interface de passagem de mensagens), tem como característica principal a comunicação entre nós através de mensagens. O modo mais simples de trocar mensagens, é através das funções de envio e recebimento de mensagens, respectivamente MPI_Send e MPI_Recv.

A ideia é muito próxima do envio de cartas do mundo real: o remetente deve especificar para a função MPI_Send, a mensagem e o destinatário. O destinatário, por sua vez, especifica para a função MPI_Recv o remetente de quem ele está esperando a carta. Um detalhe é que a função MPI_Recv é bloqueante, ou seja, o destinatário fica bloqueado até receber a mensagem que está esperando.

Broadcast

Se um processo p quiser mandar uma mensagem para todos os outros, pode utilizar a função MPI_Send para cada outro processo. Se o envio de cada uma dessas mensagens levar um tempo t e houver n processos, o tempo necessário para que todos os processos tenham a informação passada pelo processo p, será da ordem de t(n – 1). Além de não ser muito eficiente, ainda há o empecilho de o processo p estar concentrando todo o trabalho em si, o que não é interessante, uma vez que nosso objetivo é paralelizar o código.

Uma ideia é usar uma topologia em árvore para a distribuição da mensagem. Suponha que n = 8 e o processo 0 quer enviar a mensagem. A troca de mensagens segue o esquema da figura abaixo.


Topogia de árvore

Inicialmente o nó 0 envia a mensagem para o nó 1. Em um segundo momento, o nó 0 envia a mensagem para o nó 2, ao mesmo tempo em que o nó 1 envia a mensagem para o nó 3. Agora os nós 0, 1, 2 e 3 possuem a informação que o nó 0 queria transmitir. No terceiro estágio, o nó 0 envia para 0 4, o nó 1 para o 5, o 2 para o 6 e o 3 para o 7. Assim, todos os nós receberam a mensagem em 3 estágios. Não é difícil ver que o tempo gasto será proporcional à altura da árvore, que por sua vez é O(log n). Assim, o tempo total gasto é O(t log n). Na MPI, essa estratégia é implementada pela função MPI_Bcast.

Reduce

Imagine que paralelizamos um laço que fazia a soma de um vetor, distribuindo um pedaço para cada um dos processos. Depois de calculada a soma, é preciso juntar os resultados. No caso da soma, basta que cada nó envie seu resultado para o processo principal e que este os some para obter a resposta final. Assim como a versão simples do broadcast, esse esquema é proporcional ao número de nós.

Aqui, também é possível usarmos a topologia de árvore da seguinte forma: cada nó envia seu resultado para o seu predecessor na árvore. Pelo exemplo da figura anterior, o nó 0 e o nó 4 vão enviar para o nó 0. Na verdade não é preciso que o nó 0 envie o resultado para si mesmo, basta que ele receba a resposta do nó 4 e some com o valor que ele já tinha calculado. Assim, cada nó intermediário fará a soma dos seus dois filhos, de forma que no final o nó 0 conterá a soma total. Novamente conseguimos reduzir o tempo para O(t log n). Na MPI, essa abordagem é utilizada pela função MPI_Reduce.

Reduce + Broadcast

Ao realizar o reduce, o nó 0 conterá a soma total, mas os outros nós terão apenas somas parciais. Se quiséssemos que todos os nós tivessem a soma total, uma possibilidade seria o nó 0 fazer um broadcast para todos os outros nós, ou seja, um reduce seguido de um broadcast. Há um meio mais eficiente de fazer isso, através da topologia borboleta.

Topologia Borboleta

Para entender melhor esse esquema, consideremos a informação que o nó 0 envia (em verde). No primeiro estágio ele envia sua informação para o nó 4. Logo, os nós 0 e 4 têm a informação inicial do nó 0. No segundo estágio, o nó 0 envia sua informação para o nó 2, enquanto o nó 4 envia sua informação para o nó 6. Agora os nós 0, 2, 4 e 6 têm a informação do nó 0. Finalmente no estágio 3, o nó 0 envia para o nó 1, o 2 para o 3, o 4 para o 5 e o 6 para o 7. Assim, todos têm a informação inicial do nó 0. Seguindo a mesma lógica para os outros nós, concluímos que ao final do terceiro estágio, todos os nós terão informação dos outros nós. Se cada nó somar o seu conteúdo com o que receber, no final todos os nós terão as somas totais. A função MPI_Allreduce implementa essa abordagem.


Disk Graphs

Outubro 1, 2010

Semana passada teve início a série de seminários em teoria de computação dos membros do Laboratório de Otimização e Combinatória. Essas palestras ocorrerão intercaladas com os seminários do DTC (Departamento de Teoria de Computação), ocorrendo, a priori, às Sextas-feitas, 10h. Acabei estreando essa série com uma palestra intitulada “Disk Graphs”. A ideia central era definir a classe de grafos chamada disk graphs e mostrar dois problemas clássicos de teoria dos grafos sobre essa classe: o problema da clique máxima e da coloração. Neste post, vou apresentar um pequeno resumo da apresentação (disponível aqui).

Dado um conjunto de discos no plano, definimos um grafo com vértices correspondendo aos centros dos discos. Dois vértices são conectados por uma aresta se seus discos correspondentes se interceptam com área não nula. Denominamos tal grafo Disk Graph (DG).

Exemplo de Disk Graph

Um Disk Graph onde todos os discos têm mesmo tamanho é chamado de Unit Disk Graph.

Exemplo de Unit Disk Graph

No caso particular em que os discos não podem se sobrepor, apenas se tangenciar, chamamos o DG de Coin Graph (CG).

Exemplo de um Coin Graph

Em seguida falei sobre a relação entre diferentes classes de grafos. A mais interessante é devido ao Teorema de Koebe (também conhecido como circle packing theorem) que diz basicamente que grafos planares e coin graphs são equivalentes. Eu desconfiava que todo grafo planar é também um disk graph. O prof. Stolfi, que estava presente, provou com um argumento bem simples: dado um coin graph, a menor distância entre bordos de discos que não se tangenciam é positiva, enquanto a de discos que se tangenciam é exatamente 0. Assim, existe um valor suficientemente pequeno do qual podemos aumentar o raio dos discos de forma que os círculos tangentes passem a ter interseção não nula e os não tangentes assim continuem.

Problemas

Um aspecto importante ao enunciar um problema para essa classe de grafos é especificar se a entrada é dada na forma de discos ou na forma de grafo. Observe que se for dada na primeira forma, conseguimos obter a segunda. Porém, mesmo para unit disk graphs, se a entrada estiver na forma de grafo, foi provado que é NP-difícil encontrar um conjunto de discos que formem tal grafo [1]. (Para coin graphs existe um algoritmo que constrói o conjunto de discos a partir de um grafo planar [2]). Para os problemas apresentados, vamos assumir que a entrada é dada na forma de discos.

Primeiramente apresentei o problema da clique máxima para unit disk graphs. Embora seja NP-difícil encontrar a clique máxima em um grafo geral, para unit disk graphs, existe um algoritmo polinomial . Não se sabe, porém, se o problema da clique máxima para disk graphs está em P ou NP.

Depois apresentei o problema da coloração, que continua NP-difícil, mesmo para unit disk graphs e a entrada sendo dada na forma de discos. Foram desenvolvidos algoritmos aproximados e algoritmos online para unit disk graphs e disk graphs. Para unit disk graphs o melhor algoritmo aproximado até agora tem fator de aproximação 3 (limite superior), sendo que não existe algoritmo aproximado com melhor fator de aproximação menor do que 4/3 (limite inferior) a não ser que P=NP. O melhor algoritmo online tem fator de competitividade 5 (limite superior) e não existe algoritmo com fator de competitividade menor do que 2 (limite inferior) a menos que P=NP. Para disk graphs, o algoritmo aproximado tem limites inferior e superior iguais a 4/3 e 5, respectivamente, e o algoritmo online tem ambos limites inferior e superior iguais a log n, ou seja, o algoritmo online para unit disk graphs é o melhor que se pode conseguir.

Sumário com os limites dos fatores de aproximação e competitividade.

Aplicações

Na palestra acabei não falando das aplicações práticas dos disks graphs. Porém, eles são muito utilizados para projetar topologias de rede wireless. Podemos pensar que cada disco representa uma antena wireless posicionada no centro do disco, com alcance equivalente ao raio do mesmo. Assim, o problema da coloração pode ser usado para encontrar uma atribuição de frequências às antenas, considerando que há interferência entre os sinais de antenas cujos círculos se interceptam.

Referências

[1] Breu, H. and Kirkpatrick, D. G. – Unit Disk graph recognition is NP-Hard
[2] Collins, C. R. and K, Stephenson – A Circle packing algorithm