A simple and efective algorithm for the maximum happy vertices problem

• Marco Ghirardi ^[1] ; Fabio Salassa ^[1]
  1. [1] Polytechnic University of Turin

     Polytechnic University of Turin

     Torino, Italia

     
• Localización: Top, ISSN-e 1863-8279, ISSN 1134-5764, Vol. 30, Nº. 1, 2022, págs. 181-193
• Idioma: inglés
• Enlaces
  • Texto completo (pdf)
• Resumen

  • In a recent paper, a solution approach to the Maximum Happy Vertices Problem has been proposed. The approach is based on a constructive heuristic improved by a matheuristic local search phase. We propose a new procedure able to outperform the previous solution algorithm both in terms of solution quality and computational time. Our approach is based on simple ingredients implying as starting solution generator an approximation algorithm and as an improving phase a new matheuristic local search. The procedure is then extended to a multi-start confguration, able to further improve the solution quality at the cost of an acceptable increase in computational time.