Scheduling on a graph with release times

Wei Yu (), Mordecai Golin () and Guochuan Zhang ()
Additional contact information
Wei Yu: East China University of Science and Technology
Mordecai Golin: Hong Kong University of Science and Technology
Guochuan Zhang: Zhejiang University

Journal of Scheduling, 2023, vol. 26, issue 6, No 6, 580 pages

Abstract: Abstract We study a generalization of the well-known traveling salesman problem in a metric space, in which each city is associated with a release time. The salesman has to visit each city at or after its release time. There exists a naive 5/2-approximation algorithm where the salesman simply starts to route the network after all cities are released. Interestingly, this bound has never been improved for more than two decades. In this paper, we revisit the problem and achieve the following results. First, we devise an approximation algorithm with performance ratio less than 5/2 when the number of distinct release times is fixed. Then, we analyze a natural class of algorithms and show that no performance ratio better than 5/2 is possible unless the Metric TSP can be approximated with a ratio strictly less than 3/2, which is a well-known longstanding open question. Finally, we consider a special case where the graph has a heavy edge and present an approximation algorithm with performance ratio less than 5/2.

Keywords: Vehicle scheduling problem; Traveling salesman problem; Approximation algorithms; Performance ratio (search for similar items in EconPapers)
Date: 2023
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10951-021-00680-z Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jsched:v:26:y:2023:i:6:d:10.1007_s10951-021-00680-z

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10951

DOI: 10.1007/s10951-021-00680-z

Access Statistics for this article

Journal of Scheduling is currently edited by Edmund Burke and Michael Pinedo

More articles in Journal of Scheduling from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().