How much is location information worth?
In this paper we derive the worst-case ratio of an online algorithm for the Traveling Salesman Problem (TSP) with two disclosure dates. This problem, a variant of the online TSP with release dates, is characterized by the disclosure of a job's location at one point in time followed by the discl...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | |
| Format: | conferenceObject |
| Published: |
2018
|
| Online Access: | http://hdl.handle.net/10725/6880 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://papers.ssrn.com/sol3/papers.cfm?abstract_id=1303922 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | In this paper we derive the worst-case ratio of an online algorithm for the Traveling Salesman Problem (TSP) with two disclosure dates. This problem, a variant of the online TSP with release dates, is characterized by the disclosure of a job's location at one point in time followed by the disclosure of that job's release date at a later point in time. We present an online algorithm for this problem restricted to the positive real number line. We then derive the worst-case ratio of our algorithm and show that it is best-possible in two contexts - the first, one in which the amount of time between the disclosure events and release time are fixed and equal for all jobs; and a second in which the time between disclosure events varies for each job. We conclude that the value of advanced information can be attributed to the location information alone - yielding an optimal solution in favorable instances. |
|---|