{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:28:07Z","timestamp":1787509687667,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":26,"publisher":"ACM","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2005,5,22]]},"DOI":"10.1145\/1060590.1060649","type":"proceedings-article","created":{"date-parts":[[2005,8,3]],"date-time":"2005-08-03T04:31:47Z","timestamp":1123043507000},"page":"386-395","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":52,"title":["Universal approximations for TSP, Steiner tree, and set cover"],"prefix":"10.1145","author":[{"given":"Lujun","family":"Jia","sequence":"first","affiliation":[{"name":"Northeastern University, Boston, MA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guolong","family":"Lin","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, MA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Guevara","family":"Noubir","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, MA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Rajmohan","family":"Rajaraman","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, MA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ravi","family":"Sundaram","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, MA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2005,5,22]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"http:\/\/www.mathcs.emory.edu\/~mic\/interests.html.  http:\/\/www.mathcs.emory.edu\/~mic\/interests.html."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/142675.142744"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89571"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780599"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875536"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276725"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(89)90047-3"},{"key":"e_1_3_2_1_8_1","volume-title":"Online Computation and Competitive Analysis","author":"Borodin A.","year":"1998","unstructured":"A. Borodin and R. El-Yaniv . Online Computation and Competitive Analysis . Cambridge University Press , Cambridge, UK , 1998 . A. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis. Cambridge University Press, Cambridge, UK, 1998."},{"key":"e_1_3_2_1_9_1","volume-title":"Universal classes of hash functions. Journal of Computer Systems and Sciences (JCSS), 18:143--154","author":"Carter J. L.","year":"1979","unstructured":"J. L. Carter and M. N. Wegman . Universal classes of hash functions. Journal of Computer Systems and Sciences (JCSS), 18:143--154 , 1979 . J. L. Carter and M. N. Wegman. Universal classes of hash functions. Journal of Computer Systems and Sciences (JCSS), 18:143--154, 1979."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.15"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780608"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/647371"},{"key":"e_1_3_2_1_13_1","volume-title":"Computers and Intractability: A guide to the theory of NP-completeness","author":"Garey M. R.","year":"1979","unstructured":"M. R. Garey and D. S. Johnson . Computers and Intractability: A guide to the theory of NP-completeness . W. H. Freeman , San Francisco , 1979 . M. R. Garey and D. S. Johnson. Computers and Intractability: A guide to the theory of NP-completeness. W. H. Freeman, San Francisco, 1979."},{"key":"e_1_3_2_1_14_1","first-page":"499","volume-title":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-03)","author":"Goel A.","year":"2003","unstructured":"A. Goel and D. Estrin . Simultaneous optimization for concave costs: single sink aggregation or single source buy-at-bulk . In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-03) , pages 499 -- 505 , 2003 . A. Goel and D. Estrin. Simultaneous optimization for concave costs: single sink aggregation or single source buy-at-bulk. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-03), pages 499--505, 2003."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/946243.946308"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007419"},{"key":"e_1_3_2_1_17_1","first-page":"691","volume-title":"Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-04)","author":"Immorlica N.","year":"2004","unstructured":"N. Immorlica , D. R. Karger , M. Minkoff , and V. S. Mirrokni . On the costs and benefits of procrastination: Approximation algorithms for stochastic combinatorial optimization problems . In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-04) , pages 691 -- 700 , 2004 . N. Immorlica, D. R. Karger, M. Minkoff, and V. S. Mirrokni. On the costs and benefits of procrastination: Approximation algorithms for stochastic combinatorial optimization problems. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA-04), pages 691--700, 2004."},{"key":"e_1_3_2_1_18_1","first-page":"613","volume-title":"Proceedings of the Forty-First IEEE Symposium on Foundations of Computer Science (FOCS)","author":"Karger D. R.","year":"2000","unstructured":"D. R. Karger and M. Minkoff . Building steiner trees with incomplete global knowledge . In Proceedings of the Forty-First IEEE Symposium on Foundations of Computer Science (FOCS) , pages 613 -- 623 , 2000 . D. R. Karger and M. Minkoff. Building steiner trees with incomplete global knowledge. In Proceedings of the Forty-First IEEE Symposium on Foundations of Computer Science (FOCS), pages 613--623, 2000."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796586"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875567"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898719772","volume-title":"A Locality-Sensitive Approach","author":"Peleg D.","year":"2000","unstructured":"D. Peleg . Distributed Computing : A Locality-Sensitive Approach . SIAM , Philadelphia, PA , 2000 . D. Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, Philadelphia, PA, 2000."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76361"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780549"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652152"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786.2793"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/800076.802479"}],"event":{"name":"STOC05: Symposium on Theory of Computing","location":"Baltimore MD USA","acronym":"STOC05","sponsor":["ACM Association for Computing Machinery","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the thirty-seventh annual ACM symposium on Theory of computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1060590.1060649","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,8]],"date-time":"2023-01-08T03:26:05Z","timestamp":1673148365000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1060590.1060649"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,5,22]]},"references-count":26,"alternative-id":["10.1145\/1060590.1060649","10.1145\/1060590"],"URL":"https:\/\/doi.org\/10.1145\/1060590.1060649","relation":{},"subject":[],"published":{"date-parts":[[2005,5,22]]},"assertion":[{"value":"2005-05-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}