Algorithms for the Balanced Multiway Cut Problem.

• Grant number: 24/13239-6
• Support Opportunities: Scholarships in Brazil - Scientific Initiation
• Start date: October 01, 2024
• End date: September 30, 2025
• Field of knowledge: Physical Sciences and Mathematics - Computer Science - Theory of Computation
• Principal Investigator: Mário César San Felice
• Grantee: Maristella Ramalho Rangel
• Host Institution: Centro de Ciências Exatas e de Tecnologia (CCET). Universidade Federal de São Carlos (UFSCAR). São Carlos , SP, Brazil

Abstract

The Balanced Multiway Cut Problem (BMCP) is a combination of the Multiway Cut Problem and the Balanced Cut Problem, both NP-Hard variations of the classic Minimum Cut problem. In BMCP, we want to find a set of edges, with minimum cost, whose removal partitions the graph into several components, so that each component has exactly one terminal and has at most a fraction of the graph's vertices, with the set of terminal vertices and the value of the fraction given in the input. In this project we intend to study classical algorithms for the aforementioned cutting problems, and design strategies to solve the BMCP. In particular, we intend to use the Multi-Parent Biased Random-Key Genetic Algorithm with Implicit Path-Relinking (BRKGA-MP-IPR) meta-heuristic.This undergraduate research project also aims to introduce the candidate to the area of combinatorial optimization, complementing her training in computer science. The results obtained in this research must be compiled in a technical report.