M. Beristain Cortes, L. Hernando Rodriguez, J. A. Lozano Alonso
In combinatorial optimization, many algorithms treat the problem of finding optimal solutions as one of ranking, where only the relative ordering of solutions is considered, not their exact values. This implies that algorithms can exhibit similar behavior when solving different combinatorial optimization problems if the rankings of solutions are the same. In this paper, we explore the intersection of two well-known combinatorial optimization problems, the Linear Ordering Problem (LOP) and the Traveling Salesperson Problem (TSP), from the perspective of solution rankings.
We investigate the conditions under which rankings belong to both the LOP and the TSP and provide bounds on the number of such intersecting rankings. Furthermore, we propose a conjecture concerning the complexity of the set of rankings common to these two problems. Our work provides insight into how ranking-based algorithms might behave when applied to problems sharing similar solution orderings.
Palabras clave: Permutation-based combinatorial optimisation problems, rankings, linear ordering problem, asymmetric traveling salesperson problem
Programado
Heurísticas y Metaheurísticas II
10 de junio de 2025 17:10
MR 1