We consider two on-line versions of the asymmetric traveling salesman problem with triangle inequality. For the homing version, in which the salesman is required to return in the city where it started from, we give a frac(3 + sqrt(5), 2)-competitive algorithm and prove that this is best possible. For the nomadic version, the on-line analogue of the shortest asymmetric Hamiltonian path problem, we show that the competitive ratio of any on-line algorithm depends on the amount of asymmetry of the space in which the salesman moves. We also give bounds on the competitive ratio of on-line algorithms that are zealous, that is, in which the salesman cannot stay idle when some city can be served. © 2007 Elsevier B.V. All rights reserved.
Ausiello, G., Bonifaci, V., Laura, L. (2008). The on-line asymmetric traveling salesman problem. JOURNAL OF DISCRETE ALGORITHMS, 6(2), 290-298 [10.1016/j.jda.2007.03.002].
The on-line asymmetric traveling salesman problem
Bonifaci V.;
2008-01-01
Abstract
We consider two on-line versions of the asymmetric traveling salesman problem with triangle inequality. For the homing version, in which the salesman is required to return in the city where it started from, we give a frac(3 + sqrt(5), 2)-competitive algorithm and prove that this is best possible. For the nomadic version, the on-line analogue of the shortest asymmetric Hamiltonian path problem, we show that the competitive ratio of any on-line algorithm depends on the amount of asymmetry of the space in which the salesman moves. We also give bounds on the competitive ratio of on-line algorithms that are zealous, that is, in which the salesman cannot stay idle when some city can be served. © 2007 Elsevier B.V. All rights reserved.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
