Divide and Clean

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.