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!
|
| _version_ | 1864513481027354624 |
|---|---|
| author | Srour, F. Jordan |
| author2 | Zuidwijk, Rob |
| author2_role | author |
| author_facet | Srour, F. Jordan Zuidwijk, Rob |
| author_role | author |
| dc.creator.none.fl_str_mv | Srour, F. Jordan Zuidwijk, Rob |
| dc.date.none.fl_str_mv | 2018-01-08T12:07:40Z 2018-01-08T12:07:40Z 2018-01-08 |
| dc.identifier.none.fl_str_mv | http://hdl.handle.net/10725/6880 Srour, F. J., & Zuidwijk, R. A. (2008). How much is location information worth? a competitive analysis of the online traveling salesman problem with two disclosure dates. http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://papers.ssrn.com/sol3/papers.cfm?abstract_id=1303922 |
| dc.language.none.fl_str_mv | en |
| dc.publisher.none.fl_str_mv | Erasmus Research Institute of Management |
| dc.relation.none.fl_str_mv | ERIM Report Series Research in Management |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.title.none.fl_str_mv | How much is location information worth? a competitive analysis of the online traveling salesman problem with two disclosure dates |
| dc.type.none.fl_str_mv | Conference Paper / Proceeding info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/conferenceObject |
| description | 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. |
| eu_rights_str_mv | openAccess |
| format | conferenceObject |
| id | LAURepo_4ec3cd6e8ff7b9bca414848fc5279a74 |
| identifier_str_mv | Srour, F. J., & Zuidwijk, R. A. (2008). How much is location information worth? a competitive analysis of the online traveling salesman problem with two disclosure dates. |
| language_invalid_str_mv | en |
| network_acronym_str | LAURepo |
| network_name_str | Lebanese American University repository |
| oai_identifier_str | oai:laur.lau.edu.lb:10725/6880 |
| publishDate | 2018 |
| publisher.none.fl_str_mv | Erasmus Research Institute of Management |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | How much is location information worth?a competitive analysis of the online traveling salesman problem with two disclosure datesSrour, F. JordanZuidwijk, RobIn 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.N/A23 p.: ill.Includes bibliographical referencesErasmus Research Institute of Management2018-01-08T12:07:40Z2018-01-08T12:07:40Z2018-01-08Conference Paper / Proceedinginfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/conferenceObjecthttp://hdl.handle.net/10725/6880Srour, F. J., & Zuidwijk, R. A. (2008). How much is location information worth? a competitive analysis of the online traveling salesman problem with two disclosure dates.http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.phphttps://papers.ssrn.com/sol3/papers.cfm?abstract_id=1303922enERIM Report Series Research in Managementinfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/68802023-05-18T12:40:47Z |
| spellingShingle | How much is location information worth? Srour, F. Jordan |
| status_str | publishedVersion |
| title | How much is location information worth? |
| title_full | How much is location information worth? |
| title_fullStr | How much is location information worth? |
| title_full_unstemmed | How much is location information worth? |
| title_short | How much is location information worth? |
| title_sort | How much is location information worth? |
| url | 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 |