Programação matemática e imersões métricas para aproximações em problemas de corte

Abstract

Resumo: Os algoritmos de aproximação são capazes de gerar soluções próximas da ótima demandando tempo de execução polinomial. Vários dos algoritmos de aproximação existentes na literatura solucionam problemas com base em valores numéricos obtidos em soluções de programas matemáticos, como programas lineares e programas vetoriais. Os problemas do corte máximo, do corte multisseparador mínimo e do corte mais disperso podem ser modelados com programas matemáticos inteiros que, se solucionados, resultam em soluções átimas. Porem, solucionar programas matemáticos inteiros demanda tempo exponencial exigindo, assim, que sejam criados novos programas matemáticos por meio de relaxações. Uma relaxação admite valores contínuos de solução, o que torna possível encontrar a solução ótima do programa relaxado em tempo polinomial. Em contrapartida, para que sejam encontradas soluções próximas da ótima, faz-se necessárias tomadas de decisão baseadas em análises sobre as soluções dos programas relaxados. Os três problemas apresentados são modelados por programas matemáticos relaxados e solucionados com algoritmos desenvolvidos com base em análises geométricas sobre as soluções desses programas. As soluções dos programas lineares relaxados que modelam os problemas do corte multisseparador mínimo e do corte mais disperso são processadas e são visualizadas como pontos cujas distâncias são calculadas pela norma 1. Sub-rotinas que imergem espaços métricos finitos gerais em espaços métricos definidos pela norma l1 se mostraram importantes no desenvolvimento de algoritmos de aproximação. Para solucionar o problema do corte mais disperso, são utilizados algoritmos de imersão que possuem uma certa taxa de distorção das distâncias, sendo essa taxa o principal fator para a determinação da garantia de aproximação do algoritmo como um todo.

Abstract: Approximation algorithms can generate near optimal solutions requiring execution in polynomial time. Many approximation algorithms in the literature follow the idea of searching for numerical values from mathematical programming formulations, usually linear or vector programming, of the problem in consideration. The problems of maximum cut, multiway cut and sparsest cut can be modeled with integer mathematical programs that result in optimal solutions. However, solving an integer mathematical program is a NP-hard problem, so an usual approach is the creation of new mathematical programs through relaxations. A relaxation admits continuous solution, which makes possible to find the relaxed program optimal solution in polynomial time. However, in order to find near optimal solutions one should perform an analyses of this solution obtained by relaxed programs. The three problems presented here are modeled by relaxed mathematical programs and solved by algorithms based on geometric analyses on the solutions of these programs. The solutions of the relaxed linear programs that model the problems of the multiway cut and the sparsest cut are seen as points whose distances are calculated by the l1 norm. Subroutines that embed general finite metric spaces in metric spaces defined by the l1 norm proved to be important in approximation algorithms. In order to solve the sparsest cut problem, the approach is using embedding algorithms that have a certain distortion rate of the distances, being this rate the main factor determining the performance guarantee of the algorithm.