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...
Guardado en:
| Autor principal: | |
|---|---|
| Otros Autores: | , , |
| Formato: | Acta de conferencia Capítulo de libro |
| Lenguaje: | Inglés |
| Publicado: |
2009
|
| Acceso en línea: | Registro en Scopus DOI Handle Registro en la Biblioteca Digital |
| Aporte de: | Registro referencial: Solicitar el recurso aquí |
| LEADER | 06001caa a22007457a 4500 | ||
|---|---|---|---|
| 001 | PAPER-8349 | ||
| 003 | AR-BaUEN | ||
| 005 | 20230518203809.0 | ||
| 008 | 190411s2009 xx ||||fo|||| 00| 0 eng|d | ||
| 024 | 7 | |2 scopus |a 2-s2.0-70350680843 | |
| 040 | |a Scopus |b spa |c AR-BaUEN |d AR-BaUEN | ||
| 100 | 1 | |a Aprea, M. | |
| 245 | 1 | 0 | |a Discrete online TSP |
| 260 | |c 2009 | ||
| 270 | 1 | 0 | |m Aprea, M.; Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Pabellón I, (1428) Capital Federal, Argentina |
| 506 | |2 openaire |e Política editorial | ||
| 504 | |a de Paepe, W.E., (2002) Complexity Results and Competitive Analysis for Vehicle Routing Problems, , PhD thesis, Technische Universiteit Eindhoven | ||
| 504 | |a Deif, I., Bodin, L., Extension of the Clarke and Wright algorithm for solving the vehicle routing problem with backhauling (1984) Babson Conference on Software Uses in Transportation and Logistics Management, Babson Park, , MA | ||
| 504 | |a Savelsbergh, M.W.P., Local search in routing problems with time windows (1985) Annals of Operations Research, 4 (1-4), pp. 285-305 | ||
| 504 | |a Stein, D., An asymptotic, probabilistic analysis of a routing problem (1978) Mathematics of Operations Research, 3 (2), pp. 89-101 | ||
| 504 | |a Borodin, A., El-Yaniv, R., (1998) Online Computation and Competitive Analysis, , Cambridge University Press, Cambridge | ||
| 504 | |a Fiat, A., Woeginger, G.J., Online Algorithms: The State of the Art (1998) LNCS, 1442. , Springer, Heidelberg | ||
| 504 | |a Ascheuer, N., Krumke, S.O., Rambau, J., Online dial-a-ride problems: Minimizing the completion time (2000) LNCS, 1770, pp. 639-650. , Reichel, H, Tison, S, eds, STACS 2000, Springer, Heidelberg | ||
| 504 | |a Ausiello, G., Bonifaci, V., Laura, L., The on-line asymmetric traveling salesman problem (2008) Journal of Discrete Algorithms, 6 (2), pp. 290-298 | ||
| 504 | |a Ausiello, G., Feuerstein, E., Leonardi, S., Stougie, L., Talamo, M., Algorithms for the on-line travelling salesman (2001) Algorithmica, 29 (4), pp. 560-581 | ||
| 504 | |a Blom, M., Krumke, S.O., de Paepe, W., Stougie, L., The online-TSP against fair adversaries (2001) INFORMS Journal on Computing, 13 (2), pp. 138-148 | ||
| 504 | |a Lipmann, M., (2003) On-line Routing, , PhD thesis, Technische Universiteit Eindhoven | ||
| 504 | |a Psaraftis, H.N., Solomon, M.M., Magnanti, T.L., Kim, T.U., Routing and scheduling on a shoreline with release times (1990) Management Science, 36 (2), pp. 212-223 | ||
| 504 | |a Sleator, D.D., Tarjan, R.E., Amortized effciency of list update and paging rules (1985) Communications of ACM, 28, pp. 202-208 | ||
| 504 | |a Karlin, A.R., Manasse, M.S., Rudolph, L., Sleator, D.D., Competitive snoopy caching (1988) Algorithmica, 3, pp. 79-119 | ||
| 504 | |a Koutsoupias, E., Papadimitriou, C.H., Beyond competitive analysis (2000) SIAM Journal on Computing, 30 (1), pp. 300-317 | ||
| 520 | 3 | |a 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. |l eng | |
| 593 | |a Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Pabellón I, (1428) Capital Federal, Argentina | ||
| 690 | 1 | 0 | |a DISCRETE METRIC SPACES |
| 690 | 1 | 0 | |a ONLINE ALGORITHMS |
| 690 | 1 | 0 | |a TSP |
| 690 | 1 | 0 | |a COMPETITIVE ANALYSIS |
| 690 | 1 | 0 | |a COMPETITIVE RATIO |
| 690 | 1 | 0 | |a DETERMINISTIC ONLINE ALGORITHMS |
| 690 | 1 | 0 | |a DISCRETE METRIC SPACES |
| 690 | 1 | 0 | |a EMPIRICAL SIMULATIONS |
| 690 | 1 | 0 | |a LOWER BOUNDS |
| 690 | 1 | 0 | |a METRIC SPACES |
| 690 | 1 | 0 | |a ONLINE ALGORITHMS |
| 690 | 1 | 0 | |a TSP |
| 690 | 1 | 0 | |a WEIGHTED GRAPH |
| 690 | 1 | 0 | |a CONTROL THEORY |
| 690 | 1 | 0 | |a RISK PERCEPTION |
| 690 | 1 | 0 | |a SET THEORY |
| 690 | 1 | 0 | |a TOPOLOGY |
| 690 | 1 | 0 | |a TRAVELING SALESMAN PROBLEM |
| 690 | 1 | 0 | |a ALGORITHMS |
| 700 | 1 | |a Feuerstein, E. | |
| 700 | 1 | |a Sadovoy, G. | |
| 700 | 1 | |a De Loma, A.S. | |
| 711 | 2 | |c San Francisco, CA |d 15 June 2009 through 17 June 2009 |g Código de la conferencia: 77707 | |
| 773 | 0 | |d 2009 |g v. 5564 LNCS |h pp. 29-42 |p Lect. Notes Comput. Sci. |n Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |x 03029743 |w (AR-BaUEN)CENRE-983 |z 3642021573 |z 9783642021572 |t 5th International Conference on Algorithmic Aspects in Information and Management, AAIM 2009 | |
| 856 | 4 | 1 | |u https://www.scopus.com/inward/record.uri?eid=2-s2.0-70350680843&doi=10.1007%2f978-3-642-02158-9_5&partnerID=40&md5=d4bdcbdfbedef34556905042767fe9c8 |y Registro en Scopus |
| 856 | 4 | 0 | |u https://doi.org/10.1007/978-3-642-02158-9_5 |y DOI |
| 856 | 4 | 0 | |u https://hdl.handle.net/20.500.12110/paper_03029743_v5564LNCS_n_p29_Aprea |y Handle |
| 856 | 4 | 0 | |u https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_03029743_v5564LNCS_n_p29_Aprea |y Registro en la Biblioteca Digital |
| 961 | |a paper_03029743_v5564LNCS_n_p29_Aprea |b paper |c PE | ||
| 962 | |a info:eu-repo/semantics/article |a info:ar-repo/semantics/artículo |b info:eu-repo/semantics/publishedVersion | ||
| 963 | |a VARI | ||
| 999 | |c 69302 | ||