{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T14:57:20Z","timestamp":1787497040481,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":32,"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.1060597","type":"proceedings-article","created":{"date-parts":[[2005,8,3]],"date-time":"2005-08-03T04:31:47Z","timestamp":1123043507000},"page":"39-48","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":101,"title":["Approximation techniques for utilitarian mechanism design"],"prefix":"10.1145","author":[{"given":"Patrick","family":"Briest","sequence":"first","affiliation":[{"name":"Dortmund University, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Piotr","family":"Krysta","sequence":"additional","affiliation":[{"name":"Dortmund University, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Berthold","family":"V\u00f6cking","sequence":"additional","affiliation":[{"name":"RWTH Aachen, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2005,5,22]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"14th ACM-SIAM SODA","author":"Archer A.","year":"2003","unstructured":"A. Archer , C.H. Papadimitriou , K. Talwar , and \u00c9. Tardos. An approximate truthful mechanism for combinatorial auctions with single parameter agents . In 14th ACM-SIAM SODA , 2003 .]] A. Archer, C.H. Papadimitriou, K. Talwar, and \u00c9. Tardos. An approximate truthful mechanism for combinatorial auctions with single parameter agents. In 14th ACM-SIAM SODA, 2003.]]"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875583"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780616"},{"key":"e_1_3_2_1_4_1","first-page":"32","volume-title":"Proc. 34th IEEE FOCS","author":"Awerbuch B.","year":"1993","unstructured":"B. Awerbuch , Y. Azar , and S. Plotkin . Throughput-competitive online routing . In Proc. 34th IEEE FOCS , pages 32 -- 40 , 1993 .]] B. Awerbuch, Y. Azar, and S. Plotkin. Throughput-competitive online routing. In Proc. 34th IEEE FOCS, pages 32--40, 1993.]]"},{"key":"e_1_3_2_1_5_1","first-page":"15","volume-title":"LNCS","author":"Azar Y.","year":"2001","unstructured":"Y. Azar and O. Regev . Strongly polynomial algorithms for the unsplittable flow problem. In 8th IPCO , LNCS , pp. 15 -- 29 , 2001 .]] Y. Azar and O. Regev. Strongly polynomial algorithms for the unsplittable flow problem. In 8th IPCO, LNCS, pp. 15--29, 2001.]]"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/846241.846250"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30551-4_21"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/646689.703115"},{"key":"e_1_3_2_1_9_1","volume-title":"ACM-SIAM SODA","author":"Chekuri C.","year":"2000","unstructured":"C. Chekuri and S. Khanna . A PTAS for the Multiple Knapsack Problem . In ACM-SIAM SODA , 2000 .]] C. Chekuri and S. Khanna. A PTAS for the Multiple Knapsack Problem. In ACM-SIAM SODA, 2000.]]"},{"key":"e_1_3_2_1_10_1","first-page":"185","volume-title":"10th ACM-SIAM SODA","author":"Chekuri C.","year":"1999","unstructured":"C. Chekuri and S. Khanna . On Multidimensional Packing Problems . In 10th ACM-SIAM SODA , pp. 185 -- 194 , 1999 .]] C. Chekuri and S. Khanna. On Multidimensional Packing Problems. In 10th ACM-SIAM SODA, pp. 185--194, 1999.]]"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01726210"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/795664.796457"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.2307\/1914085"},{"key":"e_1_3_2_1_14_1","first-page":"1","article-title":"A survey on independent set approximations. In Proc. APPROX '98","volume":"1444","author":"Halld\u00f3rsson M.M.","year":"1998","unstructured":"M.M. Halld\u00f3rsson . A survey on independent set approximations. In Proc. APPROX '98 , Springer LNCS 1444 , pp. 1 -- 14 , 1998 .]] M.M. Halld\u00f3rsson. A survey on independent set approximations. In Proc. APPROX '98, Springer LNCS 1444, pp. 1--14, 1998.]]","journal-title":"Springer LNCS"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.17.1.36"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380825"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509956"},{"key":"e_1_3_2_1_19_1","volume-title":"6th IPCO","author":"Kolliopoulos S.G.","year":"1998","unstructured":"S.G. Kolliopoulos and C. Stein . Approximating disjoint-path problems using greedy algorithms and packing integer programs . In 6th IPCO , Springer LNCS , 1412, 1998 .]] S.G. Kolliopoulos and C. Stein. Approximating disjoint-path problems using greedy algorithms and packing integer programs. In 6th IPCO, Springer LNCS, 1412, 1998.]]"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/779928.779948"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/336992.337016"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0930"},{"key":"e_1_3_2_1_23_1","volume-title":"18th Nat'l AAAI Conf.","author":"Mu'alem A.","year":"2002","unstructured":"A. Mu'alem and N. Nisan . Truthful Approximation Mechanisms for Restricted Combinatorial Auctions . In 18th Nat'l AAAI Conf. , 2002 .]] A. Mu'alem and N. Nisan. Truthful Approximation Mechanisms for Restricted Combinatorial Auctions. In 18th Nat'l AAAI Conf., 2002.]]"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301287"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/352871.352872"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167286"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90003-7"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579324"},{"key":"e_1_3_2_1_29_1","volume-title":"ACM-SIAM SODA, 770--779","author":"Robins G.","year":"2000","unstructured":"G. Robins and A. Zelikovsky . Improved Steiner Tree Approximation in Graphs . In ACM-SIAM SODA, 770--779 , 2000 .]] G. Robins and A. Zelikovsky. Improved Steiner Tree Approximation in Graphs. In ACM-SIAM SODA, 770--779, 2000.]]"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321934"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796314240"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/646517.696327"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1540-6261.1961.tb02789.x"}],"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.1060597","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,8]],"date-time":"2023-01-08T03:25:26Z","timestamp":1673148326000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1060590.1060597"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,5,22]]},"references-count":32,"alternative-id":["10.1145\/1060590.1060597","10.1145\/1060590"],"URL":"https:\/\/doi.org\/10.1145\/1060590.1060597","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"}}]}}