Column Generation Algorithms for the Minimum Normalized Cuts problem

F. Temprano Garcia, D. Ponce López, J. Puerto Albandoz

This talk deals with the k-way normalized cut problem in complex networks. It presents a methodology using mathematical optimization to provide mixed integer linear programming formulations for the problem. The paper also develops a branch-and-price algorithm for the above mentioned problem which scales better than the compact formulations. Additionally, it is also presented a heuristic algorithm able to approximate large scale problems in those cases where the exact methods are not applicable. Extensive computational experiments assess the usefulness of these methods to solve the k-way normalized cut problem. Finally, a case study is reported on the segmentation of actual images showing the applicability of the methods in this paper to detect community structures in graphs.

Keywords: Normalized cuts, Complex networks, Community detection, Mathematical programming, Image segmentation

GT12.GELOCA1 Invited Session
November 10, 2023  9:30 AM
CC1: Audience

C. Valverde, J. Puerto Albandoz

C. Domínguez Sánchez, R. Gázquez, J. M. Morales, S. Pineda

G. González Domínguez, J. Puerto Albandoz, V. Blanco Izquierdo

B. Cobeña, I. Contreras, L. I. Martínez Merino, A. M. Rodríguez Chía