Application of Fixed Set Search to Maximal Partitioning Problem of Graphs with Supply and Demand

Abstract

Graph partitioning is a fundamental problem in computer science, with applications spanning areas such as data mining, network analysis, and the optimization of computational resources. At its core, graph partitioning involves dividing a graph’s vertices into multiple groups while minimizing the number of edges between different groups. Such partitioning is crucial for enabling efficient computations on large-scale graphs, particularly in applications that require complexity reduction, such as scientific simulations and network analyses. In this thesis we aim to adapt the FSS to the MPGSD problem, seeking to develop an efficient solution for dividing supply and demand within graph partitions. By leveraging the ability of the FSS to identify recurring patterns across various graph sizes, from small to large, and from low to high connectivity, this approach attempts to balance accuracy and computational efficiency while addressing the challenges posed by supply-demand constraints in graph partitioning. The thesis is structured as follows. Section 2 provides a detailed and formal definition of the MPGSD. In Section 3, we introduce various solution approaches for solving the MPGSD, including their algorithmic design, such as a greedy approach and the FSS. Section 4 then presents the experimental setup, covering the generation of test instances, evaluation of results and a comparison with an existing approach from the literature. Finally, Section 5 concludes the thesis with a summary of the key findings and suggestions for future research.