13 out 2020
14:00 Defesa de Mestrado Integralmente a distância
Tema
The Balanced Connected k-Partition Problem: Polyhedra and Algorithms
Aluno
Matheus Jun Ota
Orientador / Docente
Flávio Keidi Miyazawa
Breve resumo
Dado um inteiro fixo k \geq 2, o problema da k-partição conexa balanceada (BCPk) consiste em particionar um grafo em k subgrafos conexos mutuamente disjuntos e com pesos similares. Formalmente, dado um grafo conexo G com pesos não-negativos nos vértices, desejamos encontrar uma partição
\{V_i\}_{i=1}^k de V(G) tal que cada classe V_i induza um subgrafo conexo em G, e o peso da classe com menor peso é o maior possível. Esse problema, conhecido por ser NP-difícil, foi muito investigado por diversas abordagens e perspectivas: algoritmos exatos, algoritmos de aproximação para alguns valores de k e classes de grafos, variantes próximas do problema e resultados de inaproximabilidade. Do lado prático, o BCPk é utilizado para modelar problemas em processamento de imagens, análise de clusters, sistemas operacionais e robótica.
Nesse trabalho propomos duas formulações baseadas em Programação Linear Mista para o BCPk e uma formulação baseada em Programação Linear Inteira. As primeiras duas formulações são baseadas em fluxos e possuem um número polinomial de variáveis e restrições. A última formulação
contém somente variáveis binárias e um número potencialmente grande de desigualdades que podem ser separadas em tempo polinomial. Nós introduzimos novas desigualdades válidas para esse último modelo e projetamos algoritmos de separação polinomial correspondentes. Além disso, conduzimos um estudo poliédrico associado a essa formulação. Ao nosso conhecimento, esse é o primeiro estudo poliédrico para o BCPk na literatura. Utilizando a plataforma OpenStreetMap e os dados públicos
sobre a criminalidade em certas regiões, geramos novas instâncias baseadas na aplicação de patrulhamento policial. Experimentos computacionais mostram que os algoritmos exatos baseados nas nossas formulações são superiores aos melhores métodos exatos presentes na
literatura.
Banca examinadora
Titulares:
| Flávio Keidi Miyazawa | IC/UNICAMP |
| Eduardo Uchoa Barboza | UFF |
| Ricardo Fukasawa | Universidade de Waterloo/Canadá |
Suplentes:
| Eduardo Candido Xavier | IC/UNICAMP |
| Luis Augusto Angelotti Meira | FT/UNICAMP |