Reinforcement Learning in a Multi-Centrality Heuristic for Bandwidth Reduction in Sparse Matrices

The Bandwidth Minimization Problem for Sparse Matrices is a relevant NP-Hard problem in several scientific applications. Traditional approaches, such as the Cuthill-McKee algorithm, use degree centrality to minimize bandwidth. This work presents a multicentrality approach, using Reinforcement Learning (RA) with Q-Learning to optimize the selection of different centrality measures in the labeling of the vertices of a graph. The selection process is modeled as a decision-making problem, where an agent learns to choose the most effective centrality measure based on the class of the instance. The AR-based method dynamically adapts to the specific characteristics of different sparse arrays, resulting in more efficient bandwidth minimization. Experimental results show that this adaptive approach substantially improves the resolution of complex bandwidth minimization problems by surpassing traditional heuristics in computational efficiency.