<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>
handle: 10810/66011 , 20.500.11824/1025
[EN] The aim of this paper is to introduce the concept of intersection between combinatorial optimisation problems. We take into account that most algorithms, in their machinery, do not consider the exact objective function values of the solutions, but only a comparison between them. In this sense, if the solutions of an instance of a combinatorial optimisation problem are sorted into their objective function values, we can see the instances as (partial) rankings of the solutions of the search space. Working with specific problems, particularly, the linear ordering problem and the symmetric and asymmetric traveling salesman problem, we show that they can not generate the whole set of (partial) rankings of the solutions of the search space, but just a subset. First, we characterise the set of (partial) rankings each problem can generate. Secondly, we study the intersections between these problems: those rankings which can be generated by both the linear ordering problem and the symmetric/asymmetric traveling salesman problem, respectively. The fact of finding large intersections between problems can be useful in order to transfer heuristics from one problem to another, or to define heuristics that can be useful for more than one problem.
permutation-based combinatorial optimisation problems, traveling salesman problem, rankings, linear ordering problem
permutation-based combinatorial optimisation problems, traveling salesman problem, rankings, linear ordering problem
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 3 | |
popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |