Online Routing Problems: Value of Advanced Information as Improved Competitive Ratios

References

• Arora S. Polynomial-time approximation schemes for Euclidean TSP and other geometric problems. J. ACM (1998) 45(5):753–782Crossref, Google Scholar
• Ausiello G., Demange M., Laura L., Paschos V. Algorithms for the on-line quota traveling salesman problem. Inform. Processing Lett. (2004) 92(2):89–94Crossref, Google Scholar
• Ausiello G., Feuerstein E., Leonardi S., Stougie L., Talamo M. Algorithms for the on-line travelling salesman. Algorithmica (2001) 29(4):560–581Crossref, Google Scholar
• Bertsimas D. J. Probabilistic combinatorial optimization problems. (1988) . Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, MAGoogle Scholar
• Blom M., Krumke S. O., de Paepe W. E., Stougie L. The online TSP against fair adversaries. INFORMS J. Comput. (2001) 13(2):138–148Link, Google Scholar
• Blum A., Chawla S., Karger D., Lane T., Meyerson A., Minkoff M. Approximation algorithms for orienteering and discounted-reward TSP. Proc. 44th Annual IEEE Sympos. Foundations Comput. Sci. (2003) 46–55Crossref, Google Scholar
• Borodin A., El-Yaniv R.Online Computation and Competitive Analysis (1998) 1st ed.(Cambridge University Press, New York) Google Scholar
• Christofides N. Worst-case analysis of a new heuristic for the traveling salesman problem. (1976) (Carnegie-Mellon University, Pittsburg, PA) . Management Sciences Research Report 388Google Scholar
• Feuerstein E., Stougie L. On-line single-server dial-a-ride problems. Theoret. Comput. Sci. (2001) 268(1):91–105Crossref, Google Scholar
• Fiat A., Woeginger G.Online Algorithms: The State of the Art (1998) (Springer-Verlag, Germany) . Lecture Notes in Computer Science, Vol. 1442Crossref, Google Scholar
• Hall L. A., Schulz A., Shmoys D. B., Wein J. Scheduling to minimize average completion time: Off-line and on-line approximation algorithms. Math. Oper. Res. (1997) 22(3):513–544Link, Google Scholar
• Jaillet P. Probabilistic traveling salesman problems. (1985) . Ph.D. thesis, Massachusetts Institute of Technology, Cambridge, MAGoogle Scholar
• Kalyanasundaram B., Pruhs K. R. Constructing competitive tours from local information. Theoret. Comput. Sci. (1994) 130(1):125–138Crossref, Google Scholar
• Karlin A., Manasse M., Rudolph L., Sleator D. Competitive snoopy caching. Algorithmica (1988) 3:79–119Crossref, Google Scholar
• Korte B., Vygen J.Combinatorial Optimization, Theory and Algorithms (2002) 2nd ed.(Springer, Berlin, Germany) Google Scholar
• Krumke S. O., de Paepe W. E., Poensgen D., Stougie L. News from the online traveling repairman. Theoret. Comput. Sci. (2003) 295:279–294Crossref, Google Scholar
• Lawler E. L., Lenstra J. K., Kan A. H. G. Rinnooy, Shmoys D. B.The Traveling Salesman Problem, A Guided Tour of Combinatorial Optimization (1985) (John Wiley & Sons Ltd., New York) Google Scholar
• Lipmann M. The online traveling salesman problem on the line. (1999) . Master’s thesis, University of Amsterdam, The NetherlandsGoogle Scholar
• Lipmann M. On-line routing. (2003) . Ph.D. thesis, Technische Universiteit Eindhoven, The NetherlandsGoogle Scholar
• Psaraftis H., Solomon M., Magnanti T., Kim T. Routing and scheduling on a shoreline with release times. Management Sci. (1990) 36(2):212–223Link, Google Scholar
• Sleator D., Tarjan R. Amortized efficiency of list update and paging rules. Comm. ACM (1985) 28(2):202–208Crossref, Google Scholar
• Tsitsiklis J. N. Special cases of traveling salesman and repairman problems with time windows. Networks (1992) 22(3):263–282Crossref, Google Scholar