{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T09:06:56Z","timestamp":1777540016787,"version":"3.51.4"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2023,3,9]],"date-time":"2023-03-09T00:00:00Z","timestamp":1678320000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF","award":["CCF-1535989"],"award-info":[{"award-number":["CCF-1535989"]}]},{"name":"NSF","award":["CCF-1535972"],"award-info":[{"award-number":["CCF-1535972"]}]},{"name":"NSF","award":["CCF-1535972, CCF-1955703"],"award-info":[{"award-number":["CCF-1535972, CCF-1955703"]}]},{"name":"NSF CAREER","award":["CCF-1750140"],"award-info":[{"award-number":["CCF-1750140"]}]},{"name":"Indo-US Virtual Networked Joint Center on Algorithms"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2023,4,30]]},"abstract":"<jats:p>\n            Robust optimization is a widely studied area in operations research, where the algorithm takes as input a range of values and outputs a single solution that performs well for the entire range. Specifically, a robust algorithm aims to minimize\n            <jats:italic>regret<\/jats:italic>\n            , defined as the maximum difference between the solution\u2019s cost and that of an optimal solution in hindsight once the input has been realized. For graph problems in\n            <jats:bold>P<\/jats:bold>\n            , such as shortest path and minimum spanning tree, robust polynomial-time algorithms that obtain a constant approximation on regret are known. In this paper, we study robust algorithms for minimizing regret in\n            <jats:bold>NP<\/jats:bold>\n            -hard graph optimization problems, and give constant approximations on regret for the classical traveling salesman and Steiner tree problems.\n          <\/jats:p>","DOI":"10.1145\/3570957","type":"journal-article","created":{"date-parts":[[2022,12,14]],"date-time":"2022-12-14T12:15:47Z","timestamp":1671020147000},"page":"1-37","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Robust Algorithms for TSP and Steiner Tree"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6057-7619","authenticated-orcid":false,"given":"Arun","family":"Ganesh","sequence":"first","affiliation":[{"name":"UC Berkeley, Berkeley, California, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5692-7062","authenticated-orcid":false,"given":"Bruce M.","family":"Maggs","sequence":"additional","affiliation":[{"name":"Duke University and Emerald Innovations, Durham, North Carolina, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1799-6660","authenticated-orcid":false,"given":"Debmalya","family":"Panigrahi","sequence":"additional","affiliation":[{"name":"Duke University, Durham, North Carolina, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,3,9]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2007.11.008"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2008.09.012"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00011424"},{"key":"e_1_3_2_5_2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.1040.0080"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0966-8349(98)00033-3"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.12.2.104.11897"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-003-0396-4"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806769"},{"key":"e_1_3_2_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-015-0949-5"},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45471-3_18"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2012.01.005"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.42"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2018.31"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(94)00092-Q"},{"key":"e_1_3_2_16_2","doi-asserted-by":"crossref","first-page":"568","DOI":"10.1007\/978-3-642-45030-3_53","volume-title":"Algorithms and Computation","author":"Karpinski Marek","year":"2013","unstructured":"Marek Karpinski, Michael Lampis, and Richard Schmied. 2013. New inapproximability bounds for TSP. In Algorithms and Computation, Leizhen Cai, Siu-Wing Cheng, and Tak-Wah Lam (Eds.). Springer Berlin, Berlin, 568\u2013578."},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2005.11.001"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2006.09.007"},{"key":"e_1_3_2_19_2","volume-title":"Robust Discrete Optimization and Its Applications","author":"Kouvelis P.","year":"1996","unstructured":"P. Kouvelis and G. Yu. 1996. Robust Discrete Optimization and Its Applications. Springer US. 96043291"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-2620-6_6"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0969-6016(98)00023-9"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.5555\/500776"},{"key":"e_1_3_2_23_2","unstructured":"Jens Vygen. [n. d.]. New Approximation Algorithms for the TSP."},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0120913"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(01)00078-5"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(03)00373-4"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3570957","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3570957","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:37:53Z","timestamp":1750178273000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3570957"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,3,9]]},"references-count":25,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2023,4,30]]}},"alternative-id":["10.1145\/3570957"],"URL":"https:\/\/doi.org\/10.1145\/3570957","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,3,9]]},"assertion":[{"value":"2021-10-14","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-23","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-03-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}