Examinando por Autor "Robles, Marcos"

Mostrando 1 - 2 de 2

Evaluación del rendimiento de técnicas heurísticas para el S-labeling
(2024-06-19) Robles, Marcos; Cavero, Sergio; G. Pardo, Eduardo
El problema de S-labeling es un problema de etiquetado de grafos que asigna etiquetas numéricas a los vértices de un grafo, con el objetivo de minimizar una función objetivo. Concretamente, para cada par de vértices adyacentes se anota la etiqueta más pequeña del par. Una vez que se han revisado todos los pares, la función objetivo se calcula como la suma de todas las etiquetas anotadas. En este trabajo preliminar se realiza una propuesta que utiliza la metaheurística GRASP. Concretamente, se analizan un total de cuatro métodos constructivos aleatorizados, dos de ellos tomados de la literatura y dos de esta propuesta. Como método de mejora se proponen dos búsquedas locales y el uso de VND para combinarlas. El mejor algoritmo propuesto se compara con el mejor algoritmo del estado del arte (PIG), utilizando un conjunto de instancias de referencia. Los resultados muestran que uno de los métodos constructivos presentados es capaz de obtener soluciones competitivas con una desviación baja. También se comprueba que la fase de mejora es capaz de refinar las soluciones propuestas por el constructivo, obteniendo soluciones similares a las que se consiguen utilizando el algoritmo del estado del arte. Finalmente, se discuten los puntos fuertes y débiles de esta propuesta y se sugieren algunas líneas de investigación futuras.
Multi-armed bandit for the cyclic minimum sitting arrangement problem
(Elsevier, 2025-07) Robles, Marcos; Cavero, Sergio; Pardo, Eduardo G.; Cordón, Oscar
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.