@misc{10481/105426,
year = {2025},
month = {3},
url = {https://hdl.handle.net/10481/105426},
abstract = {Graphs are commonly used to represent related elements and relationships among them. Signed graphs are a special type of graphs that can represent more complex structures, such as positive or negative connections in a social network. In this work, we address a combinatorial optimization problem, known as the Cyclic Minimum Sitting Arrangement, that consists of embedding a signed input graph into a cycle host graph, trying to locate in the embedding positive connected vertices closer than negative ones. This problem is a variant of the well-known Minimum Sitting Arrangement where the host graph has the structure of a path graph. To tackle the problem, we propose an algorithm based on the Multi-Armed Bandit method that combines three greedy-randomized constructive procedures with a Variable Neighborhood Descent local search algorithm. To assess the merit of our proposal, we compare it with the state-of-the-art method. Our experiments show that our algorithm outperforms the best-known method in the literature to date, and the results are statistically significant, establishing itself as the new state of the art for the problem.},
organization = {MCIN/AEI/10.13039/501100011033 y ERDF (PID2021-125709OA-C22, PID2021-126605NB-I00)},
organization = {Generalitat Valenciana (project CIAICO/2021/224)},
organization = {Proyectos Impulso de la Universidad Rey Juan Carlos 2022  (project M2988)},
organization = {Comunidad Autónoma de Madrid - Project CIRMA-CM (Ref. TEC-2024/COM-404)},
organization = {Ministerio para la Transformación Digital y de la Función Pública [TSI-100930-2023-3 (MCA07)]},
publisher = {Elsevier},
keywords = {Signed graphs},
keywords = {Cyclic minimum sitting arrangement},
keywords = {Multi-armed bandit},
keywords = {Variable neighborhood descent},
title = {Multi-armed bandit for the cyclic minimum sitting arrangement problem},
doi = {10.1016/j.cor.2025.107034},
author = {Robles, Marcos and Cavero, Sergio and Pardo, Eduardo and Cordón García, Óscar},
}