Heuristic algorithms for the fair max-min diversity problem

• He Zheng ^[1] ; Anna Martínez Gavara ; Rafael Martí Cunquero
  1. [1] Universitat de València

     Universitat de València

     Valencia, España

     
• Localización: Actas del XVI Congreso Español de Metaheurísticas, Algoritmos Evolutivos y Bioinspirados: (MAEB 2025) 28-30 de mayo, Donostia/San Sebastián / coord. por Leticia Hernando Rodríguez , Josu Ceberio Uribe , Jon Vadillo Jueguen, 2025, ISBN 978-84-1319-656-5, págs. 9-19
• Idioma: inglés
• Enlaces
  • Texto Completo Libro
• Resumen

  • This paper investigates the Fair Max-min Diversity Problem (FMMD), which seeks to select a subset of elements that maximizes the minimum pairwise distance while ensuring fair representation across predefined groups. We formulate the problem mathematically and propose heuristic approaches to efficiently obtain high-quality solutions. Specifically, we compare the performance of the Greedy Randomized Adaptive Search Procedure (GRASP) and the Probabilistic Tabu Search (PTS).

    GRASP constructs solutions with adaptive randomness and refines them through local search, while PTS integrates probabilistic mechanisms within Tabu search to enhance diversification and intensification. Experimental evaluations on synthetic and real-world datasets demonstrate the effectiveness of both approaches, with PTS consistently achieving superior performance in terms of solution quality and computational efficiency.