Divide and Clean
Multi-Constrained Edge Partitioning and its Application in Debris Management
L.F.O. Vogels (TU Delft - Electrical Engineering, Mathematics and Computer Science)
Pinar Keskinocak – Mentor (Georgia Institute of Technology)
K. Aardal – Graduation committee member (TU Delft - Discrete Mathematics and Optimization)
More Info
expand_more
Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.
Abstract
Let G=(V,E) be a connected undirected graph, where every edge has two weights assigned to it. This thesis considers the partitioning of the edge set E of G into subsets with three objectives in mind: i) balance the total amount of the first weight among the subsets, ii) balance the total amount of the second weight among the subsets and iii) create a non-chaotic partition. Here non-chaotic means that every subset forms a distinguishable and compact subgraph. We call this Unrelated Unconnected Multi Constrained Graph Partitioning, or UUMCGP. It has applications in the collection of debris after natural disasters and in the assignment of tasks to computers in a distributed network. We are the first to define UUMCGP and we show that for specific cases close-to-optimal solutions can be obtained in polynomial time. Moreover, an algorithm is developed that gives good approximate solutions to the general case of UUMCGP. The algorithm is tested on real-life cases of debris management and gives better results than commercial solvers when they are set to find the optimal solution.