{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T03:09:52Z","timestamp":1761620992150,"version":"3.41.0"},"reference-count":28,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2008,6,1]],"date-time":"2008-06-01T00:00:00Z","timestamp":1212278400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001868","name":"National Science Council Taiwan","doi-asserted-by":"publisher","award":["NSC-94-2213-E-007-082NSC-95-2221-E-007-028"],"award-info":[{"award-number":["NSC-94-2213-E-007-082NSC-95-2221-E-007-028"]}],"id":[{"id":"10.13039\/501100001868","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2008,6]]},"abstract":"<jats:p>\n            In this article, efficient algorithms are presented for the minmax-regret 1-center and 1-median problems on a general graph and a tree with uncertain vertex weights. For the minmax-regret 1-center problem on a general graph, we improve the previous upper bound from\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>mn<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) to\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>mn<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ). For the problem on a tree, we improve the upper bound from\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) to\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ). For the minmax-regret 1-median problem on a general graph, we improve the upper bound from\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>mn<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) to\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>mn<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            +\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>3<\/jats:sup>\n            log\n            <jats:italic>n<\/jats:italic>\n            ). For the problem on a tree, we improve the upper bound from\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:sup>2<\/jats:sup>\n            <jats:italic>n<\/jats:italic>\n            ) to\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            log\n            <jats:italic>n<\/jats:italic>\n            ).\n          <\/jats:p>","DOI":"10.1145\/1367064.1367076","type":"journal-article","created":{"date-parts":[[2008,7,2]],"date-time":"2008-07-02T12:09:19Z","timestamp":1215000559000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":20,"title":["Improved algorithms for the minmax-regret 1-center and 1-median problems"],"prefix":"10.1145","volume":"4","author":[{"given":"Hung-I.","family":"Yu","sequence":"first","affiliation":[{"name":"National Tsing Hua University, Taiwan, Republic of China"}]},{"given":"Tzu-Chin","family":"Lin","sequence":"additional","affiliation":[{"name":"National Tsing Hua University, Taiwan, Republic of China"}]},{"given":"Biing-Feng","family":"Wang","sequence":"additional","affiliation":[{"name":"National Tsing Hua University, Taiwan, Republic of China"}]}],"member":"320","published-online":{"date-parts":[[2008,7,4]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Alstrup S. Lauridsen P. W. Sommerlund P. and Thorup M. 2001. Finding cores of limited length. Tech. Rep. The IT University of Copenhagen. (A preliminary version appeared in the 1997 Proceedings of the 5th International Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science vol. 1272. Springer-Verlag New York 45--54.)]]   Alstrup S. Lauridsen P. W. Sommerlund P. and Thorup M. 2001. Finding cores of limited length. Tech. Rep. The IT University of Copenhagen. (A preliminary version appeared in the 1997 Proceedings of the 5th International Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science vol. 1272. Springer-Verlag New York 45--54.)]]","DOI":"10.1007\/3-540-63307-3_47"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(00)00025-0"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(02)00384-0"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2004.12.001"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0966-8349(98)00033-3"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(99)00257-X"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.12.2.104.11897"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1002\/net.10062"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2007.02.012"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1020711416254"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0037(199803)31:2<93::AID-NET4>3.0.CO;2-E"},{"key":"e_1_2_1_12_1","first-page":"209","article-title":"Sensitivity analysis of the optimal location of a facility","volume":"33","author":"Drezner Z.","year":"1980","unstructured":"Drezner , Z. 1980 . Sensitivity analysis of the optimal location of a facility . Naval Res. Logist. Quart. 33 , 209 -- 224 .]] Drezner, Z. 1980. Sensitivity analysis of the optimal location of a facility. Naval Res. Logist. Quart. 33, 209--224.]]","journal-title":"Naval Res. Logist. Quart."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.14.3.409"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.15.3.552"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.5.2.212"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.12.3.450"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0137040"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0137041"},{"key":"e_1_2_1_19_1","unstructured":"Kouvelis P. Vairaktarakis G. and Yu G. 1994. Robust 1-median location on a tree in the presence of demand and transportation cost uncertainty. Working Paper 93\/94-3-4. Department of Management Science and Information Systems Graduate School of Business The University of Texas at Austin.]]  Kouvelis P. Vairaktarakis G. and Yu G. 1994. Robust 1-median location on a tree in the presence of demand and transportation cost uncertainty. Working Paper 93\/94-3-4. Department of Management Science and Information Systems Graduate School of Business The University of Texas at Austin.]]"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Kouvelis P. and Yu G. 1997. Robust discrete optimization and its applications Kluwer Academic Publishers Dordrecht.]]  Kouvelis P. and Yu G. 1997. Robust discrete optimization and its applications Kluwer Academic Publishers Dordrecht.]]","DOI":"10.1007\/978-1-4757-2620-6"},{"key":"e_1_2_1_21_1","volume-title":"-C","author":"Ku S.-C.","year":"2001","unstructured":"Ku , S.-C. , Lu , C.-J. , Wang , B.-F. , and Lin , T . -C . 2001 . Efficient algorithms for two generalized 2-median problems on trees. in Proceedings of the 12th International Symposium on Algorithms and Computation. Lecture Notes on Computer Science, vol. 2223 . Springer-Verlag , New York, 768--778.]] Ku, S.-C., Lu, C.-J., Wang, B.-F., and Lin, T.-C. 2001. Efficient algorithms for two generalized 2-median problems on trees. in Proceedings of the 12th International Symposium on Algorithms and Computation. Lecture Notes on Computer Science, vol. 2223. Springer-Verlag, New York, 768--778.]]"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.39.6.961"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0212052"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.13.2.85"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(85)90096-7"},{"key":"e_1_2_1_26_1","unstructured":"Nikulin Y. 2004. Robustness in combinatorial optimization and scheduling theory: an annotated bibliography. http:\/\/www.optimization-online.org\/DB_HTML\/2004\/11\/995.html.]]  Nikulin Y. 2004. Robustness in combinatorial optimization and scheduling theory: an annotated bibliography. http:\/\/www.optimization-online.org\/DB_HTML\/2004\/11\/995.html.]]"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.954619"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Weaver J. R. and Church R. L. 1983. Computational procedures of location problems on stochastic networks. Transport. Sci. 17. 168--180.]]  Weaver J. R. and Church R. L. 1983. Computational procedures of location problems on stochastic networks. Transport. Sci. 17. 168--180.]]","DOI":"10.1287\/trsc.17.2.168"}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1367064.1367076","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1367064.1367076","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:57:54Z","timestamp":1750255074000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1367064.1367076"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2008,6]]}},"alternative-id":["10.1145\/1367064.1367076"],"URL":"https:\/\/doi.org\/10.1145\/1367064.1367076","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"type":"print","value":"1549-6325"},{"type":"electronic","value":"1549-6333"}],"subject":[],"published":{"date-parts":[[2008,6]]},"assertion":[{"value":"2006-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2007-08-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-07-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}