Navegar

Colección

Datos Estadísticas

Artículo

Ausiello, G.; Feuerstein, E.; Leonardi, S.; Stougie, L.; Talamo, M. "Algorithms for the on-line travelling salesman" (2001) Algorithmica (New York). 29(4):560-581
Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

In this paper the problem of efficiently serving a sequence of requests presented in an on-line fashion located at points of a metric space is considered. We call this problem the On-Line Travelling Salesman Problem (OLTSP). It has a variety of relevant applications in logistics and robotics. We consider two versions of the problem. In the first one the server is not required to return to the departure point after all presented requests have been served. For this problem we derive a lower bound on the competitive ratio of 2 on the real line. Besides, a 2.5-competitive algorithm for a wide class of metric spaces, and a 7/3-competitive algorithm for the real line are provided. For the other version of the problem, in which returning to the departure point is required, we present an optimal 2-competitive algorithm for the above-mentioned general class of metric spaces. If in this case the metric space is the real line we present a 1.75-competitive algorithm that compares with a ≈1.64 lower bound.

Registro:

Documento: Artículo
Título:Algorithms for the on-line travelling salesman
Autor:Ausiello, G.; Feuerstein, E.; Leonardi, S.; Stougie, L.; Talamo, M.
Filiación:Dipto. di Informatica e Sistemistica, Univ. di Roma La Sapienza, via Salaria 113, 00198-Roma, Italy
Departamento de Computación, Fac. de Ciencias Exactas y Naturales, Ciudad Universitaria, 1428 Buenos Aires, Argentina
Instituto de Ciencias, Universidad de General Sarmiento, Rxa 850, (1663) San Miguel, Buenos Aires, Argentina
Department of Mathematics, Eindhoven University of Technology, PO Box 513, 5600MB Eindhoven, Netherlands
Palabras clave:Competitive analysis; On-line algorithms; Travelling salesman problem; Vehicle routing; Logistics; Problem solving; Robotics; Traveling salesman problem; On-line algorithms; Algorithms
Año:2001
Volumen:29
Número:4
Página de inicio:560
Página de fin:581
DOI: http://dx.doi.org/10.1007/s004530010071
Título revista:Algorithmica (New York)
Título revista abreviado:Algorithmica (New York)
ISSN:01784617
CODEN:ALGOE
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_01784617_v29_n4_p560_Ausiello

Referencias:

  • Alborzi, H., Torng, E., Uthaisombut, P., Wagner, S., The k-client problem (1997) Proc. Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 73-82
  • Atallah, M., Kosaraju, S., Efficient solutions for some transportation problems with application to minimizing robot arm travel (1988) SIAM Journal on Computing, 17, pp. 849-869
  • Ben-David, S., Borodin, A., Karp, R.M., Tardos, G., Widgerson, A., On the power of randomization in on-line algorithms (1990) Proc 22nd Annual ACM Symposium on Theory of Computing, pp. 379-386
  • Borodin, A., El-Yaniv, R., (1998) On-Line Computation and Competitive Analysis, , Cambridge University Press, Cambridge
  • El-Yaniv, R., Fiat, A., Karp, R.M., Turpin, G., Competitive analysis of financial games (1992) Proc. 33rd Annual Symposium on Foundations of Computer Science, pp. 327-333
  • Frederickson, G., A note on the complexity of a simple transportation problem (1993) SIAM Journal on Computing, 22 (1), pp. 57-61
  • Frederickson, G., Guan, D., Preemptive ensemble motion planning on a tree (1992) SIAM Journal on Computing, 21 (6), pp. 1130-1152
  • Frederickson, G., Hecht, M., Kim, C., Approximation algorithms for some routing problems (1978) SIAM Journal on Computing, 7 (2), pp. 178-193
  • Garey, M., Johnson, D., (1979) Computers and Intractability: A Guide to the Theory of NP-Completeness, , Freeman, San Francisco, CA
  • Graham, R.L., Bounds for certain multiprocessing anomalies (1966) Bell System Technical Journal, 45, pp. 1563-1581
  • Johnson, D.S., (1973) Near Optimal Bin-Packing Algorithms, , Doctoral thesis, MIT
  • Kalyanasundaram, B., Pruhs, K.R., Constructing competitive tours from local information (1993) Proc. 20th International Colloquium on Automata, Languages and Programming, pp. 102-113. , LNCS 700, Springer-Verlag, Berlin
  • Karuno, Y., Nagamochi, H., Ibaraki, T., Vehicle scheduling on a tree with release times and handling times (1993) Proc. 4th International Symposium on Algorithms and Computation (ISAAC '93), pp. 486-495. , LNCS 762, Springer-Verlag, Berlin
  • Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G., Shmoys, D.B., (1985) The Travelling Salesman Problem: A Guided Tour of Combinatorial Optimization, , Wiley, Chichester
  • Manasse, M., McGeoch, L.A., Sleator, D., Competitive algorithms for server problems (1990) Journal of Algorithms, 11, pp. 208-230
  • Psaraftis, H., Solomon, M., Magnanti, T., Kim, T., Routing and scheduling on a shoreline with release times (1990) Management Science, 36 (2), pp. 212-223
  • Shmoys, D.B., Wein, J., Williamson, D.P., Scheduling parallel machines on-line (1991) Proc. 32nd Annual Symposium on Foundations of Computer Science, pp. 131-140
  • Sleator, D., Tarjan, R., Amortized efficiency of list update and paging algorithms (1985) Communications of the ACM, 28, pp. 202-208
  • Sleator, D., Tarjan, R., Self-adjusting binary search trees (1985) Journal of the ACM, 32, pp. 652-686
  • Solomon, M., Algorithms for the vehicle routing and scheduling problem with time window constraints (1987) Operations Research, 35 (2), pp. 254-265
  • Solomon, M., Desrosiers, J., Time window constrained routing and scheduling problems: A survey (1988) Transportation Science, 22, pp. 1-13

Citas:

---------- APA ----------
Ausiello, G., Feuerstein, E., Leonardi, S., Stougie, L. & Talamo, M. (2001) . Algorithms for the on-line travelling salesman. Algorithmica (New York), 29(4), 560-581.
http://dx.doi.org/10.1007/s004530010071
---------- CHICAGO ----------
Ausiello, G., Feuerstein, E., Leonardi, S., Stougie, L., Talamo, M. "Algorithms for the on-line travelling salesman" . Algorithmica (New York) 29, no. 4 (2001) : 560-581.
http://dx.doi.org/10.1007/s004530010071
---------- MLA ----------
Ausiello, G., Feuerstein, E., Leonardi, S., Stougie, L., Talamo, M. "Algorithms for the on-line travelling salesman" . Algorithmica (New York), vol. 29, no. 4, 2001, pp. 560-581.
http://dx.doi.org/10.1007/s004530010071
---------- VANCOUVER ----------
Ausiello, G., Feuerstein, E., Leonardi, S., Stougie, L., Talamo, M. Algorithms for the on-line travelling salesman. Algorithmica (New York). 2001;29(4):560-581.
http://dx.doi.org/10.1007/s004530010071