Discrete online TSP

In this paper we introduce a discrete version of the online traveling salesman problem (DOLTSP). We represent the metric space using a weighted graph, where the server is allowed to modify its route only at the vertices. This limitation directly affects the capacity of the server to react and increa...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autor principal:	Aprea, Mauro
Publicado:	2009
Materias:	Discrete metric spaces Online algorithms TSP Competitive analysis Competitive ratio Deterministic online algorithms Empirical simulations Lower bounds Metric spaces Weighted graph Control theory Risk perception Set theory Topology Traveling salesman problem Algorithms
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v5564LNCS_n_p29_Aprea http://hdl.handle.net/20.500.12110/paper_03029743_v5564LNCS_n_p29_Aprea
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_03029743_v5564LNCS_n_p29_Aprea
record_format	dspace
spelling	paper:paper_03029743_v5564LNCS_n_p29_Aprea2023-06-08T15:28:31Z Discrete online TSP Aprea, Mauro Discrete metric spaces Online algorithms TSP Competitive analysis Competitive ratio Deterministic online algorithms Discrete metric spaces Empirical simulations Lower bounds Metric spaces Online algorithms TSP Weighted graph Control theory Risk perception Set theory Topology Traveling salesman problem Algorithms In this paper we introduce a discrete version of the online traveling salesman problem (DOLTSP). We represent the metric space using a weighted graph, where the server is allowed to modify its route only at the vertices. This limitation directly affects the capacity of the server to react and increases the risk related to each decision. We prove lower bounds on the performance of deterministic online algorithms in different scenarios of DOLTSP, and we present distinct algorithms for the problem, some of them achieving the best possible performance. We measure the performance of the algorithms using competitive analysis, the most widely accepted method for evaluating online algorithms. Besides, we perform an empirical simulation on paths, generating a significant set of instances and measuring the quality of the solutions given by each algorithm. Our experiments show that algorithms with the best competitive ratio do not have the best performance in practice. © 2009 Springer Berlin Heidelberg. Fil:Aprea, M. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2009 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v5564LNCS_n_p29_Aprea http://hdl.handle.net/20.500.12110/paper_03029743_v5564LNCS_n_p29_Aprea
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	Discrete metric spaces Online algorithms TSP Competitive analysis Competitive ratio Deterministic online algorithms Discrete metric spaces Empirical simulations Lower bounds Metric spaces Online algorithms TSP Weighted graph Control theory Risk perception Set theory Topology Traveling salesman problem Algorithms
spellingShingle	Discrete metric spaces Online algorithms TSP Competitive analysis Competitive ratio Deterministic online algorithms Discrete metric spaces Empirical simulations Lower bounds Metric spaces Online algorithms TSP Weighted graph Control theory Risk perception Set theory Topology Traveling salesman problem Algorithms Aprea, Mauro Discrete online TSP
topic_facet	Discrete metric spaces Online algorithms TSP Competitive analysis Competitive ratio Deterministic online algorithms Discrete metric spaces Empirical simulations Lower bounds Metric spaces Online algorithms TSP Weighted graph Control theory Risk perception Set theory Topology Traveling salesman problem Algorithms
description	In this paper we introduce a discrete version of the online traveling salesman problem (DOLTSP). We represent the metric space using a weighted graph, where the server is allowed to modify its route only at the vertices. This limitation directly affects the capacity of the server to react and increases the risk related to each decision. We prove lower bounds on the performance of deterministic online algorithms in different scenarios of DOLTSP, and we present distinct algorithms for the problem, some of them achieving the best possible performance. We measure the performance of the algorithms using competitive analysis, the most widely accepted method for evaluating online algorithms. Besides, we perform an empirical simulation on paths, generating a significant set of instances and measuring the quality of the solutions given by each algorithm. Our experiments show that algorithms with the best competitive ratio do not have the best performance in practice. © 2009 Springer Berlin Heidelberg.
author	Aprea, Mauro
author_facet	Aprea, Mauro
author_sort	Aprea, Mauro
title	Discrete online TSP
title_short	Discrete online TSP
title_full	Discrete online TSP
title_fullStr	Discrete online TSP
title_full_unstemmed	Discrete online TSP
title_sort	discrete online tsp
publishDate	2009
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v5564LNCS_n_p29_Aprea http://hdl.handle.net/20.500.12110/paper_03029743_v5564LNCS_n_p29_Aprea
work_keys_str_mv	AT apreamauro discreteonlinetsp
_version_	1768544180202635264

Discrete online TSP

Ejemplares similares