{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:12:08Z","timestamp":1750306328226,"version":"3.41.0"},"reference-count":15,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2016,3,16]],"date-time":"2016-03-16T00:00:00Z","timestamp":1458086400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGecom Exch."],"published-print":{"date-parts":[[2016,3,16]]},"abstract":"<jats:p>We show that algorithms that follow the relax-and-round paradigm translate approximation guarantees into Price of Anarchy guarantees, provided that the rounding is oblivious and the relaxation is smooth. We use this meta result to obtain simple, near-optimal mechanisms for a broad range of optimization problems such as combinatorial auctions, the maximum traveling salesman problem, and packing integer programs. In each case the resulting mechanism matches or beats the performance guarantees of known mechanisms.<\/jats:p>","DOI":"10.1145\/2904104.2904107","type":"journal-article","created":{"date-parts":[[2016,3,18]],"date-time":"2016-03-18T13:50:44Z","timestamp":1458309044000},"page":"22-25","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Algorithms as mechanisms"],"prefix":"10.1145","volume":"14","author":[{"given":"Paul","family":"D\u00fctting","sequence":"first","affiliation":[{"name":"ETH Z\u00fcrich"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Kesselheim","sequence":"additional","affiliation":[{"name":"Max-Planck-Institut f\u00fcr Informatik"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"\u00c9va","family":"Tardos","sequence":"additional","affiliation":[{"name":"Cornell University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,3,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13036-6_28"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/110843654"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2764468.2764507"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/070680977"},{"key":"e_1_2_1_5_1","first-page":"103","article-title":"A unifying hierarchy of valuations with complements and substitutes","volume":"21","author":"Feige U.","year":"2014","journal-title":"Electronic Colloquium on Computational Complexity"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.27.4.799"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.76"},{"volume-title":"Proc. of the 21st Symposium on Discrete Algorithms. 537--553","author":"Lucier B.","key":"e_1_2_1_8_1"},{"volume-title":"Proc. of the 29th International Symposium on Theoretical Aspects of Computer Science. 501--506","year":"2012","author":"Paluch K. E.","key":"e_1_2_1_9_1"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90003-7"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579324"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536485"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2229012.2229078"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488635"},{"key":"e_1_2_1_15_1","unstructured":"Vazirani V. V. 2001. Approximation Algorithms. Springer-Verlag New York Inc. New York NY USA.   Vazirani V. V. 2001. Approximation Algorithms. Springer-Verlag New York Inc. New York NY USA."}],"container-title":["ACM SIGecom Exchanges"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2904104.2904107","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2904104.2904107","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:54:34Z","timestamp":1750222474000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2904104.2904107"}},"subtitle":["the price of anarchy of relax-and-round"],"short-title":[],"issued":{"date-parts":[[2016,3,16]]},"references-count":15,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,3,16]]}},"alternative-id":["10.1145\/2904104.2904107"],"URL":"https:\/\/doi.org\/10.1145\/2904104.2904107","relation":{},"ISSN":["1551-9031"],"issn-type":[{"type":"electronic","value":"1551-9031"}],"subject":[],"published":{"date-parts":[[2016,3,16]]},"assertion":[{"value":"2016-03-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}