Approximation algorithms for time-dependent orienteering. (English) Zbl 1043.90076
Summary: The time-dependent orienteering problem is dual to the time-dependent traveling salesman problem. It consists of visiting a maximum number of sites within a given deadline. The traveling time between two sites is in general dependent on the starting time. For any \(\varepsilon >0\), we provide a \((2+\varepsilon)\)-approximation algorithm for the time-dependent orienteering problem which runs in polynomial time if the ratio between the maximum and minimum traveling time between any two sites is constant. No prior upper approximation bounds were known for this time-dependent problem.
References:
| [1] | Arkin, E. M.; Mitchell, J. S.B.; Narasimhan, G., Resource-constrained geometric network optimization, (Proceedings 14th ACM Symposium on Computational Geometry (June 6-10, 1998)), 307-316 |
| [2] | Awerbuch, B.; Azar, Y.; Blum, A.; Vempala, S., Improved approximation guarantees for minimum-weight \(k\)-trees and prize-collecting salesman, (Proceedings 27th Annual ACM Symp. Theory Comput. (STOC’95) (1995)), 277-283 · Zbl 0920.90136 |
| [3] | Balas, E., The prize collecting traveling salesperson problem, Networks, 19, 621-636 (1989) · Zbl 0676.90089 |
| [4] | Bockenhauer, H. J.; Hromkovic, J.; Klasing, R.; Seibert, S.; Unger, W., An improved lower bound on the approximability of metric TSP and approximation algorithms for the TSP with sharpened triangle inequality, Inform. Process. Lett., 75, 3, 133-138 (2000) · Zbl 1338.68289 |
| [5] | Broden, B., Time Dependent Traveling Salesman Problem, M.Sc. thesis (2000), Department of Computer Science, Lund University: Department of Computer Science, Lund University Sweden |
| [7] | Czumaj, A.; Finch, I.; Gasieniec, L.; Gibbons, A.; Leng, P.; Rytter, W.; Zito, M., Efficient web searching using temporal factors, (Dehne, F.; Gupta, A.; Sack, J.-R.; Tamassia, R., Proceedings of the 6th Workshop on Algorithms and Data Structures (WADS). Proceedings of the 6th Workshop on Algorithms and Data Structures (WADS), Lecture Notes in Comput. Sci., 1663 (1999), Springer: Springer Berlin), 294-305 · Zbl 0983.68045 |
| [8] | Engebretsen, L., An explicit lower bound for TSP with distances one and two, (Proceedings 16th Annual Symposium on Theoretical Aspects of Computer Science. Proceedings 16th Annual Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Comput. Sci. (1999), Springer: Springer Berlin), 373-382 |
| [9] | Golden, B. G.; Levy, L.; Vohra, R., The orienteering problem, Naval Res. Logist, 34, 307-318 (1991) · Zbl 0647.90099 |
| [10] | Hammar, M.; Nilsson, B., Approximation results for kinetic variants of TSP, (Proceedings of the 26th International Colloquium on Automata, Languages, and Programming (ICALP’99). Proceedings of the 26th International Colloquium on Automata, Languages, and Programming (ICALP’99), Lecture Notes in Comput. Sci., 1644 (1999), Springer: Springer Berlin), 392-401 |
| [11] | Johnson, D. S.; Minkoff, M.; Phillips, S., The Prize Collecting Steiner Tree Problem: Theory and practice, (Proc. 11th Ann. ACM-SIAM Symp. on Discrete Algorithms (2000)), 760-769 · Zbl 0956.68112 |
| [12] | Marathe, M. V.; Ravi, R.; Sundaram, R.; Ravi, S. S.; Rosenkrantz, D. J.; Hunt, H. B., Bicriteria network design problems, J. Algorithms, 28, 142-171 (1998) · Zbl 0906.68076 |
| [13] | Papadimitriou, C. H.; Vempala, S., On the approximability of the traveling salesman problem, (Proceedings of the 32nd ACM STOC (2000)), 126-133 · Zbl 1296.68083 |
| [14] | Papadimitriou, C. H.; Yannakakis, M., The traveling salesman problem with distances one and two, Math. Oper. Res. 18, 1, 1-11 (1993) · Zbl 0778.90057 |
| [15] | Spieksma, F. C.R., On the approximability of an interval scheduling problem, J. Scheduling, 2, 215-227 (1999) · Zbl 0938.90034 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
