Multi-armed bandit for the cyclic minimum sitting arrangement problem

Resumen

Los grafos se usan comúnmente para representar elementos relacionados y relaciones entre ellos. Los grafos con signo son un tipo especial de grafos que pueden representar estructuras más complejas, como conexiones positivas o negativas en una red social. En este trabajo, abordamos un problema de optimización combinatoria, conocido como Arreglo Mínimo de Sentados Cíclico, que consiste en embeber un grafo de entrada con signo en un grafo huésped cíclico, tratando de localizar en el embebido vértices conectados positivamente más cerca que los negativos. Este problema es una variante del bien conocido Arreglo Mínimo de Sentados donde el grafo huésped tiene la estructura de un grafo camino. Para abordar el problema, proponemos un algoritmo basado en el método Bandido Multi-Brazo que combina tres procedimientos constructivos codiciosos-aleatorizados con un algoritmo de búsqueda local de Descenso de Vecindarios Variables. Para evaluar el mérito de nuestra propuesta, la comparamos con el método estado del arte. Nuestros experimentos muestran que nuestro algoritmo supera al mejor método conocido en la literatura hasta la fecha, y los resultados son estadísticamente significativos, estableciéndose como el nuevo estado del arte para el problema.

Citar Esta Publicación

Robles, M., Cavero, S., Pardo, E. G., & Cordón, O. (2025). Multi-armed bandit for the cyclic minimum sitting arrangement problem. Computers & Operations Research, 179, 107034.