Multi-escala é uma técnica geral para resolver todo tipo de problema computacional que envolve algum tipo de espaço geométrico. Ela têm sido usada com sucesso em reconhecimento de padrões, reconstrução objetos fragmentados, busca de imagens por conteúdo, integração de equações diferenciais, e muito mais.
Nesta palestra vou descrever alguns exemplos ilustrativos de aplicação dessa técnica em vários problemas que encontrei ao longo dos últimos dez anos.

Nesta apresentação, veremos sobre o projeto de mecanismos em teoria dos jogos e algumas aplicações em leilões. Nos restringiremos a mecanismos determinísticos. Veremos aplicações em leilões simples, na construção de um caminho mínimo e em leilões combinatoriais.

Disk graphs são uma classe de grafos induzidos por um conjunto de discos no plano. Os centros dos discos formam seus vértices e existe uma aresta entre dois vértices se seus discos correspondentes se interceptam. Quando todo os discos têm mesmo raio, o grafo formado é chamado de unit disk graph. No caso em que sobreposição não é permitida, apenas tangência, temos o chamado coin graph.

Nesta apresentação vamos focar no estudo das propriedades geométricas dos discos que permitem algoritmos mais eficientes ou melhores fatores de aproximação para este tipo de grafo. Inicialmente vamos apresentar relações entre algumas classes de grafos e os disk graphs. Discutiremos então dois problemas clássicos em grafos: o da clique máxima e do número cromático.

Nesta apresentação, veremos como provar resultados de inaproximabilidade de problemas difíceis usando classes de complexidade não-uniformes. Em particular, mostraremos como construir uma instância do problema de soma de subconjuntos e sua resolução por um leilão combinatorial que pode ser resolvido em tempo polinomial, resultando em $NP \subset P/Poly$ (afirmação que acredita-se ser improvável). Para isso, mostraremos como construir este leilão aproximado por um fator $n/(1 + \epsilon)$ usando o conceito de Dimensão Vapnik-Chervonenkis (VC).

O problema da reconstrução filogenética é o problema de construir uma árvore que represente a história evolutiva de um conjunto de espécies de interesse. É um problema importante em biologia molecular e em bioinformática.

Neste seminário apresento uma contextualização da reconstrução filogenética e resultados iniciais a respeito de uma variação do problema.

O problema de Acesso à Lista é um dos mais estudados na área de algoritmos online, surgindo no contexto da gerência de dicionários e na compressão de dados. Nas últimas décadas os algoritmos para este problema foram estudados através da análise competitiva. Esta é uma análise de pior caso que qualifica os algoritmos através da chamada razão de competitividade.

Embora existam algoritmos com razões de competitividade constantes para o problema de Acesso à Lista, estas estão muito distantes do desempenho dos algoritmos na prática. Um motivo para esta diferença é que na prática as instâncias deste problema apresentam localidade. Assim, surgiram estudos que consideram o efeito da localidade na análise dos algoritmos.

O algoritmo mais famoso para o problema de Acesso à Lista é o Move-to-Front (MTF). Trata-se de um algoritmo simples que move para o início da lista todo item que é acessado. MTF apresenta razão de competitividade 2, mas tem um desempenho muito melhor na prática. Vamos mostrar que, quando considerada a localidade, MTF apresenta razões de competitividade muito melhores.

Estamos interessados em construir um escalonamento de tarefas sobre uma grade computacional. Neste caso usuários doam recursos de processamento para a grade, de tal forma que o processamento disponível ao longo do tempo é imprevisível e variável. Podemos assumir a existência de $m$ máquinas com tempo de processamento variável e $n$ tarefas. Em cada intervalo de tempo $t$, a máquina $i$ consegue executar $s_{it}$ instruções e cada tarefa tem seu tamanho dado pelo número de instruções necessárias para executa-la.

Neste seminário apresentaremos alguns resultados de aproximação para este problema.

No problema do geométrico, dado um polígono com buracos que também são polígonos e um objeto de área não-nula chamado cortador, queremos encontrar uma curva fechada que ao ser percorrida pelo cortador a área coberta é exatamente a do polígono de entrada.

Neste seminário será apresentado um algoritmo exato e um aproximado para a variação deste problema em que os polígonos são retilineares e há custo nas conversões.

O Problema de Empacotamento em Múltiplas Faixas é uma generalização do Problema de Empacotamento em Faixa. Dado um conjunto de retângulos de altura e largura $\le 1$, o objetivo é encontrar um empacotamento ortogonal sem rotações em $k$ faixas de largura 1 e altura ilimitada de modo a minimizar a altura máxima.

Neste seminário apresentaremos alguns resultados de aproximação para este problema.