Divide and Clean

Divide and Clean: Multi-Constrained Edge Partitioning and its Application in Debris Management

Vogels, Lucas (TU Delft Electrical Engineering, Mathematics and Computer Science)

Keskinocak, Pinar (mentor)
Aardal, K.I. (graduation committee)

Delft University of Technology

Applied Mathematics

2019-12-19

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.

graph partitioning
debris management
multi-resource generalized assignment problem
edge partitioning

http://resolver.tudelft.nl/uuid:85729e1f-214b-4c87-9747-ed08371637bc

Student theses

master thesis

© 2019 Lucas Vogels