{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,27]],"date-time":"2025-10-27T21:05:01Z","timestamp":1761599101802,"version":"3.41.0"},"reference-count":11,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2010,6,1]],"date-time":"2010-06-01T00:00:00Z","timestamp":1275350400000},"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":[[2010,6]]},"abstract":"<jats:p>Applications in complex systems such as the Internet have spawned a recent interest in studying situations involving multiple agents with their individual cost or utility functions. In this paper, we introduce an algorithmic framework for studying combinatorial optimization problems in the presence of multiple agents with submodular cost functions. We study several fundamental covering problems in this framework and establish upper and lower bounds on their approximability.<\/jats:p>","DOI":"10.1145\/1980534.1980542","type":"journal-article","created":{"date-parts":[[2011,5,17]],"date-time":"2011-05-17T12:59:03Z","timestamp":1305637143000},"page":"1-4","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Approximability of combinatorial problems with multi-agent submodular cost functions"],"prefix":"10.1145","volume":"9","author":[{"given":"Gagan","family":"Goel","sequence":"first","affiliation":[{"name":"Georgia Institute of Technology"}]},{"given":"Chinmay","family":"Karande","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology"}]},{"given":"Pushkar","family":"Tripathi","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology"}]},{"given":"Lei","family":"Wang","sequence":"additional","affiliation":[{"name":"Georgia Institute of Technology"}]}],"member":"320","published-online":{"date-parts":[[2010,6]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72792-7_15"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2005.162.439"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.40"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Goemans M. X. Harvey N. J. A. Iwata S. and Mirrokni V. S. 2009. Approximating submodular functions everywhere. In SODA. 535--544.   Goemans M. X. Harvey N. J. A. Iwata S. and Mirrokni V. S. 2009. Approximating submodular functions everywhere. In SODA . 535--544.","DOI":"10.1137\/1.9781611973068.59"},{"key":"e_1_2_1_5_1","unstructured":"Hayrapetyan A. Swamy C. and Tardos \u00e9. 2005. Network design for information networks. In SODA. 933--942.   Hayrapetyan A. Swamy C. and Tardos \u00e9. 2005. Network design for information networks. In SODA . 933--942."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510017"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2007.06.019"},{"key":"e_1_2_1_8_1","unstructured":"Sharma Y. Swamy C. and Williamson D. P. 2007. Approximation algorithms for prize collecting forest problems with submodular penalty functions. In SODA. 1275--1284.   Sharma Y. Swamy C. and Williamson D. P. 2007. Approximation algorithms for prize collecting forest problems with submodular penalty functions. In SODA . 1275--1284."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-6377(03)00062-2"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.66"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374389"}],"container-title":["ACM SIGecom Exchanges"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1980534.1980542","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1980534.1980542","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:22:52Z","timestamp":1750278172000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1980534.1980542"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6]]},"references-count":11,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,6]]}},"alternative-id":["10.1145\/1980534.1980542"],"URL":"https:\/\/doi.org\/10.1145\/1980534.1980542","relation":{},"ISSN":["1551-9031"],"issn-type":[{"type":"electronic","value":"1551-9031"}],"subject":[],"published":{"date-parts":[[2010,6]]},"assertion":[{"value":"2010-06-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}