LV
L.F.O. Vogels
info
Please Note
<p>This page displays the records of the person named above and is not linked to a unique person identifier. This record may need to be merged to a profile.</p>
1 records found
1
Divide and Clean
Multi-Constrained Edge Partitioning and its Application in Debris Management
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.
...
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.