An ad-hoc algorithm to find the minimum winning coalition. (2023). Lincolao-Venegas, I.; Lobos-Pacheco, E.; Mirabal, P.; Parra-Riquelme, A.; Quiroz-Valenzuela, V., & Rojas-Mora, J.


Finding the minimum winning coalition (MWC) is a particular case of clustering problems constrained on the clusters’ size. As such, this problem is NP-Hard, posing an exciting challenge in optimization. In this work, we present a new adhoc algorithm to solve the MWC problem, which identifies the same MWC found by a genetic algorithm implemented under the same platform. The algorithm works deterministically and achieves a solution in tenths of a second for a real problem with high complexity, the political spectrum of the House of the 75° Congress of the USA as calculated with DW-Nominate. Hence, the solution time is two orders of magnitude better than the average time it takes for the genetic algorithm to find it.

Otras publicaciones