The balanced connected k-partition problem [recurso eletrônico] : polyhedra and algorithms = O problema da k-partição conexa balanceada : poliedros e algoritmos
Matheus Jun Ota
DISSERTAÇÃO
Inglês
T/UNICAMP Ot1b
[O problema da k-partição conexa balanceada ]
Campinas, SP : [s.n.], 2020.
1 recurso online (83 p.) : il., digital, arquivo PDF.
Orientadores: Flávio Keidi Miyazawa, Phablo Fernando Soares Moura
Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação
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...
Ver mais
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$ induz um subgrafo conexo em $G$, e o peso da classe com menor peso seja 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$ ou classes de grafos, variantes próximas do problema e resultados de inaproximabilidade. Do ponto de vista 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 e uma formulação baseada em Programação Linear Inteira para o BCPk. 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. Introduzimos novas desigualdades válidas para esse último modelo e projetamos algoritmos de separação polinomial correspondentes. Além disso, apresentamos resultados poliédricos associados a essa formulação. Pelo que sabemos, não existe resultados dessa natureza 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
Ver menos
Abstract: Given a fixed integer $k \geq 2$, the balanced connected $k$-partition problem (BCPk) consists of partitioning a graph into $k$ mutually vertex-disjoint subgraphs of similar weight. More formally, given a connected graph $G$ with non-negative weights on the vertices, we want to find a...
Ver mais
Abstract: Given a fixed integer $k \geq 2$, the balanced connected $k$-partition problem (BCPk) consists of partitioning a graph into $k$ mutually vertex-disjoint subgraphs of similar weight. More formally, given a connected graph $G$ with non-negative weights on the vertices, we want to find a partition $\{V_i\}_{i=1}^k$ of~$V(G)$ such that each class $V_i$ induces a connected subgraph of $G$, and the weight of a class with the minimum weight is as large as possible. This problem, known to be NP-hard, has been largely investigated under different approaches and perspectives: exact algorithms, approximation algorithms for some values of $k$ or special classes of graphs, close variants of the problem, and inapproximability results. On the practical side, BCPk is used to model many applications arising in image processing, cluster analysis, operating systems and robotics. We propose two MILP formulations and one ILP formulation for BCPk. The first two are based on flows and have a polynomial number of constraints and variables. The last formulation contains only binary variables and a potentially large number of constraints that can be separated in polynomial time in the corresponding linear relaxation. We introduce new valid inequalities and design polynomial-time separation algorithms for them. Furthermore, we present polyhedral results based on this ILP formulation. To our knowledge, this is the first polyhedral study for BCPk in the literature. Using the OpenStreetMap platform and public crime data, we generated new instances based on a police patrolling application. Our computational experiments show that the exact algorithms based on the proposed formulations outperform the other approaches presented in the literature
Ver menos
Requisitos do sistema: Software para leitura de arquivo em PDF
The balanced connected k-partition problem [recurso eletrônico] : polyhedra and algorithms = O problema da k-partição conexa balanceada : poliedros e algoritmos
Matheus Jun Ota
The balanced connected k-partition problem [recurso eletrônico] : polyhedra and algorithms = O problema da k-partição conexa balanceada : poliedros e algoritmos
Matheus Jun Ota