Online traveling salesman problems with rejection options
In this article, we consider online versions of the traveling salesman problem on metric spaces for which requests to visit points are not mandatory. Associated with each request is a penalty (if rejected). Requests are revealed over time (at their release dates) to a server who must decide which re...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Wiley Blackwell
2015
|
| Online Access: | http://hdl.handle.net/1721.1/100431 https://orcid.org/0000-0002-8585-6566 |
| _version_ | 1811082784647675904 |
|---|---|
| author | Jaillet, Patrick Lu, Xin Xin, Lu |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Jaillet, Patrick Lu, Xin Xin, Lu |
| author_sort | Jaillet, Patrick |
| collection | MIT |
| description | In this article, we consider online versions of the traveling salesman problem on metric spaces for which requests to visit points are not mandatory. Associated with each request is a penalty (if rejected). Requests are revealed over time (at their release dates) to a server who must decide which requests to accept and serve in order to minimize a linear combination of the time to serve all accepted requests and the total penalties of all rejected requests. In the basic online version of the problem, a request can be accepted any time after its release date. In the real-time online version, a request must be accepted or rejected at the time of its release date. For the basic version, we provide a best possible 2-competitive online algorithm for the problem on a general metric space. For the real-time version, we first consider special metric spaces: on the nonnegative real line, we provide a best possible 2.5-competitive polynomial time online algorithm; on the real line, we prove a Ω(√ln n) lower bound of 2.64 on any competitive ratios and give a 3-competitive online algorithm. We then consider the case of a general metric space and prove a inline image lower bound on the competitive ratio of any online algorithms. Finally, among the restricted class of online algorithms with prior knowledge about the total number of requests n, we propose an asymptotically best possible O(√ln n)-competitive algorithm. |
| first_indexed | 2024-09-23T12:08:38Z |
| format | Article |
| id | mit-1721.1/100431 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T12:08:38Z |
| publishDate | 2015 |
| publisher | Wiley Blackwell |
| record_format | dspace |
| spelling | mit-1721.1/1004312022-09-28T00:31:27Z Online traveling salesman problems with rejection options Jaillet, Patrick Lu, Xin Xin, Lu Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Massachusetts Institute of Technology. Operations Research Center Jaillet, Patrick Xin, Lu In this article, we consider online versions of the traveling salesman problem on metric spaces for which requests to visit points are not mandatory. Associated with each request is a penalty (if rejected). Requests are revealed over time (at their release dates) to a server who must decide which requests to accept and serve in order to minimize a linear combination of the time to serve all accepted requests and the total penalties of all rejected requests. In the basic online version of the problem, a request can be accepted any time after its release date. In the real-time online version, a request must be accepted or rejected at the time of its release date. For the basic version, we provide a best possible 2-competitive online algorithm for the problem on a general metric space. For the real-time version, we first consider special metric spaces: on the nonnegative real line, we provide a best possible 2.5-competitive polynomial time online algorithm; on the real line, we prove a Ω(√ln n) lower bound of 2.64 on any competitive ratios and give a 3-competitive online algorithm. We then consider the case of a general metric space and prove a inline image lower bound on the competitive ratio of any online algorithms. Finally, among the restricted class of online algorithms with prior knowledge about the total number of requests n, we propose an asymptotically best possible O(√ln n)-competitive algorithm. United States. Office of Naval Research (Grant N00014-09-1-0326) United States. Office of Naval Research (Grant N00014-12-1-0033) United States. Air Force Office of Scientific Research (Grant FA9550-10-1-0437) 2015-12-18T15:19:11Z 2015-12-18T15:19:11Z 2014-08 2013-03 Article http://purl.org/eprint/type/JournalArticle 00283045 1097-0037 http://hdl.handle.net/1721.1/100431 Jaillet, Patrick, and Xin Lu. “Online Traveling Salesman Problems with Rejection Options.” Networks 64, no. 2 (August 11, 2014): 84–95. https://orcid.org/0000-0002-8585-6566 en_US http://dx.doi.org/10.1002/net.21559 Networks Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Wiley Blackwell MIT web domain |
| spellingShingle | Jaillet, Patrick Lu, Xin Xin, Lu Online traveling salesman problems with rejection options |
| title | Online traveling salesman problems with rejection options |
| title_full | Online traveling salesman problems with rejection options |
| title_fullStr | Online traveling salesman problems with rejection options |
| title_full_unstemmed | Online traveling salesman problems with rejection options |
| title_short | Online traveling salesman problems with rejection options |
| title_sort | online traveling salesman problems with rejection options |
| url | http://hdl.handle.net/1721.1/100431 https://orcid.org/0000-0002-8585-6566 |
| work_keys_str_mv | AT jailletpatrick onlinetravelingsalesmanproblemswithrejectionoptions AT luxin onlinetravelingsalesmanproblemswithrejectionoptions AT xinlu onlinetravelingsalesmanproblemswithrejectionoptions |