{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T10:32:25Z","timestamp":1740133945835,"version":"3.37.3"},"reference-count":15,"publisher":"World Scientific Pub Co Pte Ltd","issue":"07","funder":[{"DOI":"10.13039\/501100004663","name":"Ministry of Science and Technology, Taiwan","doi-asserted-by":"publisher","award":["110-2223-E-007-001","110-2811-E-007-507"],"award-info":[{"award-number":["110-2223-E-007-001","110-2811-E-007-507"]}],"id":[{"id":"10.13039\/501100004663","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2023,11]]},"abstract":"<jats:p> With a rapidly growing attention on the development of learning-augmented algorithms, we revisit the classical online traveling salesman problem (OLTSP) from the perspective of such learning approaches. A learning-augmented online algorithm, or simply an online algorithm with predictions, considers how to improve its competitive performance with theoretical guarantees by forecasting the information of future requests, e.g., their release time or locations in the OLTSP. In this study, we investigate the OLTSP on the real line, motivated by the parcel picking problem in a smart warehouse, which aims at scheduling a route for a server (saying, a Kiva robot), starting at the origin, serving all online requests and returning to the origin such that the completion time is minimized. Each online request is released over time on the real line and the server moves back and forth along the line with unit speed. <\/jats:p><jats:p> We mainly focus on zealous algorithms, a special type of online algorithms for the OLTSP which never allow the sever to wait if there are still unserved requests, and exploit a specific forecasting strategy, called online predictions, which makes a sequence of predictions one by one in an online manner. In order to ensure better competitive performance, we particularly explore the worst-case scenarios that restrict the power of such predictions. Based on the discussion, we make an assumption in which online predictions are guaranteed to be useful, and devise a learning-augmented algorithm with [Formula: see text]-robustness and [Formula: see text]-consistency, [Formula: see text], comparing to the previous lower bound of [Formula: see text], where [Formula: see text] and [Formula: see text] which indicate prediction errors are sufficiently small constants. Moreover, we also conduct numerical experiments to demonstrate the practical effectiveness of the proposed algorithm. <\/jats:p>","DOI":"10.1142\/s0129054123470020","type":"journal-article","created":{"date-parts":[[2023,7,26]],"date-time":"2023-07-26T09:44:40Z","timestamp":1690364680000},"page":"825-851","source":"Crossref","is-referenced-by-count":0,"title":["Online Predictions for Online TSP on the Line"],"prefix":"10.1142","volume":"34","author":[{"given":"Jian-Xi","family":"Shao","sequence":"first","affiliation":[{"name":"Department of Industrial Engineering and Engineering Management, National Tsing Hua University, Hsinchu 30013, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ya-Chun","family":"Liang","sequence":"additional","affiliation":[{"name":"Department of Industrial Engineering and Engineering Management, National Tsing Hua University, Hsinchu 30013, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chung-Shou","family":"Liao","sequence":"additional","affiliation":[{"name":"Department of Industrial Engineering and Engineering Management, National Tsing Hua University, Hsinchu 30013, Taiwan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2023,7,25]]},"reference":[{"issue":"4","key":"S0129054123470020BIB001","doi-asserted-by":"crossref","first-page":"560","DOI":"10.1007\/s004530010071","volume":"29","author":"Ausiello G.","year":"2001","journal-title":"Algorithmica"},{"volume-title":"36th Annual Conference on Neural Information Processing Systems","year":"2022","author":"Bernardini G.","key":"S0129054123470020BIB002"},{"issue":"1","key":"S0129054123470020BIB003","first-page":"1","volume":"17","author":"Bjelde A.","year":"2020","journal-title":"ACM Transactions on Algorithms (TALG)"},{"issue":"2","key":"S0129054123470020BIB004","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1287\/ijoc.13.2.138.10517","volume":"13","author":"Blom M.","year":"2001","journal-title":"INFORMS Journal on Computing"},{"issue":"2","key":"S0129054123470020BIB005","doi-asserted-by":"crossref","first-page":"204","DOI":"10.1006\/jagm.1995.1034","volume":"19","author":"Blum A.","year":"1995","journal-title":"Journal of Algorithms"},{"issue":"4","key":"S0129054123470020BIB006","doi-asserted-by":"crossref","first-page":"639","DOI":"10.1006\/jcss.2001.1773","volume":"63","author":"Feige U.","year":"2001","journal-title":"Journal of Computer and System Sciences"},{"issue":"2","key":"S0129054123470020BIB007","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1002\/(SICI)1098-2418(200003)16:2<195::AID-RSA5>3.0.CO;2-A","volume":"16","author":"Feige U.","year":"2000","journal-title":"Random Structures & Algorithms"},{"key":"S0129054123470020BIB008","first-page":"2319","volume-title":"International Conference on Machine Learning","author":"Gollapudi S.","year":"2019"},{"volume-title":"International Conference on Learning Representations","year":"2019","author":"Hsu C.-Y.","key":"S0129054123470020BIB010"},{"key":"S0129054123470020BIB012","doi-asserted-by":"crossref","first-page":"1859","DOI":"10.1137\/1.9781611975994.114","volume-title":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Lattanzi S.","year":"2020"},{"key":"S0129054123470020BIB013","first-page":"3296","volume-title":"International Conference on Machine Learning","author":"Lykouris T.","year":"2018"},{"volume-title":"Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis","year":"2017","author":"Mitzenmacher M.","key":"S0129054123470020BIB015"},{"issue":"7","key":"S0129054123470020BIB016","doi-asserted-by":"crossref","first-page":"33","DOI":"10.1145\/3528087","volume":"65","author":"Mitzenmacher M.","year":"2022","journal-title":"Communications of the ACM"},{"key":"S0129054123470020BIB017","first-page":"9661","volume-title":"Advances in Neural Information Processing Systems","author":"Purohit M.","year":"2018"},{"issue":"3","key":"S0129054123470020BIB018","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1145\/3232535","volume":"62","author":"Roughgarden T.","year":"2019","journal-title":"Communications of the ACM"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054123470020","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,26]],"date-time":"2023-10-26T04:53:17Z","timestamp":1698295997000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/10.1142\/S0129054123470020"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,7,25]]},"references-count":15,"journal-issue":{"issue":"07","published-print":{"date-parts":[[2023,11]]}},"alternative-id":["10.1142\/S0129054123470020"],"URL":"https:\/\/doi.org\/10.1142\/s0129054123470020","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"type":"print","value":"0129-0541"},{"type":"electronic","value":"1793-6373"}],"subject":[],"published":{"date-parts":[[2023,7,25]]}}}