Complexity indices for the traveling salesman problem continued

We consider the symmetric traveling salesman problem (TSP) with instances represented by complete graphs G with distances between cities as edge weights. A complexity index is an invariant of an instance I by which we predict the execution time of an exact TSP algorithm for I. In the paper [5] we ha...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Cvetković Dragoš, Dražić Zorica, Kovačević-Vujčić Vera
Formato:	article
Lenguaje:	EN
Publicado:	University of Belgrade 2021
Materias:	traveling salesman problem complexity index concorde tsp solver random instances correlation Management information systems T58.6-58.62
Acceso en línea:	https://doaj.org/article/144606d72995418ca2635c9208125a5b
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:144606d72995418ca2635c9208125a5b
record_format	dspace
spelling	oai:doaj.org-article:144606d72995418ca2635c9208125a5b2021-12-01T13:00:34ZComplexity indices for the traveling salesman problem continued0354-02431820-743X10.2298/YJOR201121014Chttps://doaj.org/article/144606d72995418ca2635c9208125a5b2021-01-01T00:00:00Zhttp://www.doiserbia.nb.rs/img/doi/0354-0243/2021/0354-02432100014C.pdfhttps://doaj.org/toc/0354-0243https://doaj.org/toc/1820-743XWe consider the symmetric traveling salesman problem (TSP) with instances represented by complete graphs G with distances between cities as edge weights. A complexity index is an invariant of an instance I by which we predict the execution time of an exact TSP algorithm for I. In the paper [5] we have considered some short edge subgraphs of G and defined several new invariants related to their connected components. Extensive computational experiments with instances on 50 vertices with the uniform distribution of integer edge weights in the interval [1,100] show that there exists correlation between the sequences of selected invariants and the sequence of execution times of the well-known TSP Solver Concorde. In this paper we extend these considerations for instances up to 100 vertices.Cvetković DragošDražić ZoricaKovačević-Vujčić VeraUniversity of Belgradearticletraveling salesman problemcomplexity indexconcorde tsp solverrandom instancescorrelationManagement information systemsT58.6-58.62ENYugoslav Journal of Operations Research, Vol 31, Iss 4, Pp 471-481 (2021)
institution	DOAJ
collection	DOAJ
language	EN
topic	traveling salesman problem complexity index concorde tsp solver random instances correlation Management information systems T58.6-58.62
spellingShingle	traveling salesman problem complexity index concorde tsp solver random instances correlation Management information systems T58.6-58.62 Cvetković Dragoš Dražić Zorica Kovačević-Vujčić Vera Complexity indices for the traveling salesman problem continued
description	We consider the symmetric traveling salesman problem (TSP) with instances represented by complete graphs G with distances between cities as edge weights. A complexity index is an invariant of an instance I by which we predict the execution time of an exact TSP algorithm for I. In the paper [5] we have considered some short edge subgraphs of G and defined several new invariants related to their connected components. Extensive computational experiments with instances on 50 vertices with the uniform distribution of integer edge weights in the interval [1,100] show that there exists correlation between the sequences of selected invariants and the sequence of execution times of the well-known TSP Solver Concorde. In this paper we extend these considerations for instances up to 100 vertices.
format	article
author	Cvetković Dragoš Dražić Zorica Kovačević-Vujčić Vera
author_facet	Cvetković Dragoš Dražić Zorica Kovačević-Vujčić Vera
author_sort	Cvetković Dragoš
title	Complexity indices for the traveling salesman problem continued
title_short	Complexity indices for the traveling salesman problem continued
title_full	Complexity indices for the traveling salesman problem continued
title_fullStr	Complexity indices for the traveling salesman problem continued
title_full_unstemmed	Complexity indices for the traveling salesman problem continued
title_sort	complexity indices for the traveling salesman problem continued
publisher	University of Belgrade
publishDate	2021
url	https://doaj.org/article/144606d72995418ca2635c9208125a5b
work_keys_str_mv	AT cvetkovicdragos complexityindicesforthetravelingsalesmanproblemcontinued AT draziczorica complexityindicesforthetravelingsalesmanproblemcontinued AT kovacevicvujcicvera complexityindicesforthetravelingsalesmanproblemcontinued
_version_	1718405159590035456

Complexity indices for the traveling salesman problem continued

Ejemplares similares