Primeira melhoria do algoritmo fundamental em 10 anos

O problema de fluxo máximo, que é onipresente na análise de redes, programação e logística, agora pode ser resolvido de forma mais eficiente do que nunca.

O problema do fluxo máximo, ou fluxo máximo, é um dos problemas mais básicos em ciência da computação: Primeiro resolvidos durante os preparativos para a ponte aérea de Berlim, é um componente de muitos dos problemas logísticos e um grampo de cursos introdutórios sobre algoritmos. Durante décadas foi objeto de pesquisa de destaque, com novos algoritmos que resolvem-se mais e mais eficiente que saem uma ou duas vezes por ano. Mas como o problema tornou-se compreender melhor, o ritmo da inovação retardado. Agora, no entanto, pesquisadores do MIT, em conjunto com os colegas na Universidade de Yale e da Universidade do Sul da Califórnia, têm demonstrado a primeira melhoria do algoritmo de fluxo máximo em 10 anos.

O problema de fluxo máximo é, grosso modo, para calcular a quantidade máxima de "coisas" que podem se mover de uma extremidade de uma rede para outra, dadas as limitações de capacidade das ligações da rede. As coisas poderiam ser os pacotes de dados que viajam através da Internet ou caixas de mercadorias em circulação ao longo das rodovias; limitações nos links "poderia ser a largura de banda das ligações à Internet ou a velocidade média do tráfego em estradas congestionadas.

Mais tecnicamente, o problema tem a ver com o que os matemáticos chamam de gráficos. Um grafo é uma coleção de vértices e arestas, que são geralmente descritos como círculos e as linhas conectando-os. O esquema padrão de uma rede de comunicações é um gráfico, como, por exemplo, uma árvore genealógica. No problema de fluxo máximo, um dos vértices do gráfico - um dos círculos - é designado a fonte, onde todas as coisas vem, outra é designada a fuga, onde todo o material é dirigido. Cada uma das extremidades - as linhas que ligam os círculos - tem uma capacidade associada, ou quanta coisa pode passar por cima dele.

Hidden fluxos

gráficos Tal modelo do mundo real de transporte e redes de comunicação de uma forma bastante simples. Mas as suas aplicações são na verdade muito mais ampla ", explica Jonathan Kelner, um professor assistente de matemática aplicada no MIT, que ajudou a liderar o novo trabalho. "Um número muito, muito grande de problemas de otimização, se você olhar para o algoritmo mais rápido agora para solucioná-los, eles usam o fluxo máximo", diz Kelner. Fora da análise de rede, uma pequena lista de aplicativos que usam o fluxo máximo pode incluir programação da linha aérea, análise de circuitos, distribuição de tarefas em supercomputadores, processamento de imagem digital, e alinhamento das seqüências de DNA.

Tradicionalmente, explica Kelner, algoritmos para o cálculo do fluxo máximo consideraria um caminho através do gráfico de cada vez. Se ele tivesse capacidade não utilizada, o algoritmo simplesmente enviar mais coisas sobre ele e ver o que aconteceu. Melhorias na eficiência dos algoritmos veio inteligentes e mais inteligentes maneiras de selecionar a ordem em que os caminhos foram explorados.

Gráficos de grades

Mas Kelner, CSAIL estudante de graduado Aleksander Madry, matemática undergrad Paulo Christiano e professores Daniel Spielman e Shanghua Teng, respectivamente, Yale e USC, têm feito uma abordagem fundamentalmente nova para o problema. Eles representam o gráfico como uma matriz, que é matemática falar para uma rede grande de números. Cada nó no gráfico é atribuído uma linha e uma coluna da matriz, o número em que uma linha e uma coluna se cruzam representa a quantidade de coisas que podem ser transferidos entre dois nós.

No ramo da matemática conhecido como álgebra linear, uma linha de uma matriz pode também ser interpretada como uma equação matemática, e as ferramentas de álgebra linear permite a solução simultânea de todas as equações incorporados por todos de uma matriz de linhas. Por várias vezes modificando os números na matriz e re-solução das equações, os pesquisadores avaliar efetivamente o gráfico inteiro de uma vez. Esta abordagem, que Kelner irá descrever em uma palestra na MIT's Stata Center em 28 de setembro, acaba por ser mais eficiente do que tentar trilhar um por um.

Se N é o número de nós em um gráfico, e L é o número de ligações entre eles, em seguida, a execução do anterior algoritmo de fluxo máximo foi o mais rápido proporcional a (N + L)^(02/03). A execução do novo algoritmo é proporcional a (N + L)^(03/04). Para uma rede como a Internet, que tem centenas de bilhões de nós, o novo algoritmo poderia resolver o problema de fluxo máximo, centenas de vezes mais rápido que seu antecessor.

A praticidade imediata do algoritmo, no entanto, não é o que impressiona John Hopcroft, a IBM Professor de Engenharia e Matemática Aplicada da Universidade de Cornell e um receptor do Prêmio Turing, o maior prêmio em ciência da computação. "Meu palpite é que este quadro especial vai ser aplicável a uma vasta gama de outros problemas", diz Hopcroft. "É uma técnica radicalmente nova. Quando há uma ruptura dessa natureza, em geral, então, forma-se uma subdisciplina, e em quatro ou cinco anos, uma série de resultados sairão. "