Algoritmos Desinformados para Roteamentos em Redes
Autores
|
6096 |
2787,410,242
|
|
|
6097 |
2787,410,242
|
|
|
6098 |
2787,410,242
|
Informações:
Publicações do PESC
O problema do roteamento desinformado consiste em selecionar caminhos para rotear commodities sem considerar a carga da rede. Neste cenário, a escolha dos caminhos depende somente da origem e destino de cada commodity e da topologia da rede.
Este trabalho considera o problema do roteamento desinformado com o objetivo de minimizar o congestionamento em redes direcionadas ou não, com capacidades nas arestas ou nos vértices. Nesta dissertação é feito um estudo mais detalhado de dois algoritmos aproximativos baseados na constituição de uma árvore de decomposição, ambos para a versão do problema com redes não-direcionadas que possuem capacidades nas arestas. Os algoritmos e as provas de suas razões de competitividade são apresentados em notação unificada, fazendo com que os resultados sejam facilmente comparáveis.
The oblivious routing problem consists of selecting paths to route commodities in a networlt, without ever considering the load of the network. More precisely, the choice of paths depends only on the source and destination o£ each commodity and on the networlt topology.
This work considers the oblivious routing problem that selects paths so as to minimize the congestion on the network linlts or nodes, on either directed or undirected networlts. This dissertation reviews two approximation algorithms for the edge capacitated version of this problem which are based on the construction of decomposition trees. In an attempt to make the results easier to read and compare, the algorithms and the proofs for their approximation guarantees are presented in a unified nmnner.