Um arredondamento probabilístico aplicado à árvore de Steiner com qualidade de serviço

Resumo:

O problema da árvore de Steiner com qualidade de serviço (QoS Steiner Tree Problem) aparece no contexto de envio amplo (broadcast) de mensagens a partir de um ponto de uma rede para diversos servidores que têm, cada um, uma velocidade diferente de recebimento. A velocidade de recebimento de um servidor estabelece a largura de banda desejada no caminho da fonte das mensagens até o servidor em questão.

Formalmente, o problema consiste no seguinte: dado um grafo G, com custos não-negativo nas arestas, um vértice r (a fonte das mensagens) e, para cada vértice v, um número não-negativo que representa a sua velocidade de recepção, encontrar uma árvore geradora de valor mínimo, onde o valor de uma árvore é a soma do custo de cada uma de suas arestas multiplicada pela largura de banda atribuída à aresta. A largura de banda de uma aresta e na árvore T é o maior valor de velocidade de recepção de um vértice que usa e para chegar a r em T (ou seja, e está no caminho de r ao vértice em T).

Este problema é NP-difícil, já que tem o problema de Steiner como caso particular. Recentemente apareceram os primeiros algoritmos de aproximação para o problema com razão constante. O melhor deles tem razão de aproximação 3.802 e utiliza algoritmos de aproximação para árvores de Steiner.

Neste seminário apresentaremos um algoritmo de aproximação primal-dual que atinge uma razão de 4.311. O algoritmo utiliza uma técnica de arredondamento probabilístico introduzida por Charikar, Naor e Schieber. Essa técnica é bastante simples, porém não é óbvia, e resulta em razões de aproximação bem melhores que o jeito mais óbvio de aplicar arredondamento.

Esse é um trabalho conjunto com Gruia Calinescu (Chicago).