A carregar...
Publicação
Beyond Complexity: An Experimental Study of Maximum Flow Algorithms
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 2.64 MB | Adobe PDF |
Autores
Orientador(es)
Resumo(s)
The maximum flow problem was formulated in 1954 and consists of taking the maximum
amount of something from one point to another through a set of connections, whilst always
respecting each connection’s restrictions. It is easy to think about real-life situations in
which we could apply maximum flow algorithms such as transportation networks and
water distribution. Thus, this problem has become very popular with applications in
numerous domains.
Since its creation, many researchers have devoted their efforts to trying to come up
with different approaches to get to a solution that is better than the already existing ones.
Although all the algorithms covered in this dissertation presented, at the time they were
published, an improvement to the theoretical time complexity, this does not always mean
they ran faster in all conditions. Therefore, one of the purposes of this dissertation is to
better understand the differences between the theoretical and the experimental results.
To achieve that, we empirically tested the Edmonds-Karp, the Dinic’s, recursive and
iterative versions, and two variants of the push-relabel algorithm, one with first in first
out (FIFO) and another with the highest label protocol. These five algorithms were tested
on several networks with different characteristics, including both artificial and real-life
scenarios. Furthermore, another contribution of this dissertation is the simplification and
explanation of some procedures of the Chen et al.’s algorithm, a recent work that achieved
an incredibly low time complexity.
O problema do fluxo máximo foi formulado em 1954 e consiste em levar a quantidade máxima de algo de um ponto para outro através de um conjunto de conexões, respeitando sempre as restrições de cada conexão. É fácil identificar situações da vida real às quais é possível aplicar algoritmos de fluxo máximo, como as redes de transporte e de distribuição de água. Deste modo, este problema tornou-se muito popular, com aplicações em diversos domínios. Desde a sua criação, muitos investigadores têm dedicado os seus esforços a tentar encontrar diferentes abordagens para chegar a uma solução que seja melhor do que as já existentes. Embora todos os algoritmos abordados nesta dissertação tenham apresentado, na altura da sua publicação, uma melhoria teórica em termos de complexidade temporal, tal nem sempre significa um menor tempo de execução em todas as condições. Assim, um dos objetivos desta dissertação é compreender melhor as diferenças entre os resultados teóricos e os experimentais. Para este efeito, testámos empiricamente os algoritmos de Edmonds-Karp, de Dinic, versão recursiva e iterativa, e duas variantes do algoritmo push- relabel, uma com FIFO e outra com o protocolo da etiqueta mais alta. Estes cinco algoritmos foram testados em várias redes com diferentes características, incluindo cenários artificiais e reais. Ademais, outra contribuição desta dissertação é a simplificação e explicação de alguns procedimentos do algoritmo de Chen et al., um trabalho recente que atingiu uma complexidade temporal incrivelmente baixa.
O problema do fluxo máximo foi formulado em 1954 e consiste em levar a quantidade máxima de algo de um ponto para outro através de um conjunto de conexões, respeitando sempre as restrições de cada conexão. É fácil identificar situações da vida real às quais é possível aplicar algoritmos de fluxo máximo, como as redes de transporte e de distribuição de água. Deste modo, este problema tornou-se muito popular, com aplicações em diversos domínios. Desde a sua criação, muitos investigadores têm dedicado os seus esforços a tentar encontrar diferentes abordagens para chegar a uma solução que seja melhor do que as já existentes. Embora todos os algoritmos abordados nesta dissertação tenham apresentado, na altura da sua publicação, uma melhoria teórica em termos de complexidade temporal, tal nem sempre significa um menor tempo de execução em todas as condições. Assim, um dos objetivos desta dissertação é compreender melhor as diferenças entre os resultados teóricos e os experimentais. Para este efeito, testámos empiricamente os algoritmos de Edmonds-Karp, de Dinic, versão recursiva e iterativa, e duas variantes do algoritmo push- relabel, uma com FIFO e outra com o protocolo da etiqueta mais alta. Estes cinco algoritmos foram testados em várias redes com diferentes características, incluindo cenários artificiais e reais. Ademais, outra contribuição desta dissertação é a simplificação e explicação de alguns procedimentos do algoritmo de Chen et al., um trabalho recente que atingiu uma complexidade temporal incrivelmente baixa.
Descrição
Palavras-chave
Maximum flow Algorithms Time complexity Experimental analysis Comparative analysis