{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:32:48Z","timestamp":1759847568253},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2009,1,30]],"date-time":"2009-01-30T00:00:00Z","timestamp":1233273600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2010,10]]},"DOI":"10.1007\/s10878-009-9209-x","type":"journal-article","created":{"date-parts":[[2009,1,29]],"date-time":"2009-01-29T17:56:25Z","timestamp":1233251785000},"page":"259-284","source":"Crossref","is-referenced-by-count":8,"title":["Cost sharing and strategyproof mechanisms for set cover games"],"prefix":"10.1007","volume":"20","author":[{"given":"Xiang-Yang","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zheng","family":"Sun","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Weizhao","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wei","family":"Lou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2009,1,30]]},"reference":[{"key":"9209_CR1","first-page":"294","volume-title":"SODA \u201908: Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms","author":"S Albers","year":"2008","unstructured":"Albers S (2008) On the value of coordination in network design. In: SODA \u201908: Proceedings of the nineteenth annual ACM-SIAM symposium on discrete algorithms. Society for Industrial and Applied Mathematics, Philadelphia, pp\u00a0294\u2013303"},{"key":"9209_CR2","doi-asserted-by":"crossref","first-page":"36","DOI":"10.1016\/S0899-8256(03)00176-3","volume":"47","author":"A Archer","year":"2004","unstructured":"Archer A, Feigenbaum J, Krishnamurthy A, Sami R, Shenker S (2004) Approximation and collusion in multicast cost sharing. Games Econ Behav 47:36\u201371","journal-title":"Games Econ Behav"},{"key":"9209_CR3","unstructured":"Chawla S, Kitchin D, Rajan U, Ravi R, Sinha A (2002) Profit maximizing mechanisms for the extended multicasting game. Tech rep CMU-CS-02-164, Carnegie Mellon University"},{"key":"9209_CR4","doi-asserted-by":"crossref","first-page":"233","DOI":"10.1287\/moor.4.3.233","volume":"4","author":"V Chv\u00e1tal","year":"1979","unstructured":"Chv\u00e1tal V (1979) A greedy heuristic for the set-covering problem. Math Oper Res 4:233\u2013235","journal-title":"Math Oper Res"},{"key":"9209_CR5","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/BF01726210","volume":"11","author":"EH Clarke","year":"1971","unstructured":"Clarke EH (1971) Multipart pricing of public goods. Public Choice 11:17\u201333","journal-title":"Public Choice"},{"key":"9209_CR6","doi-asserted-by":"crossref","unstructured":"Devanur N, Mihail M, Vazirani V (2003) Strategyproof cost-sharing mechanisms for set cover and facility location games. In: Proceedings of the 4th ACM conference on electronic commerce, pp\u00a0108\u2013114","DOI":"10.1145\/779928.779942"},{"key":"9209_CR7","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige U (1998) A threshold of for approximating set cover. J ACM 45:634\u2013652","journal-title":"J ACM"},{"key":"9209_CR8","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1006\/jcss.2001.1754","volume":"63","author":"J Feigenbaum","year":"2001","unstructured":"Feigenbaum J, Papadimitriou CH, Shenker S (2001) Sharing the cost of multicast transmissions. J Comput Syst Sci 63:21\u201341","journal-title":"J Comput Syst Sci"},{"key":"9209_CR9","doi-asserted-by":"crossref","unstructured":"Feigenbaum J, Papadimitriou C, Sami R, Shenker S (2002) A BGP-based mechanism for lowest-cost routing. In: Proceedings of the 21st annual ACM symposium on principles of distributed computing, pp\u00a0173\u2013182","DOI":"10.1145\/571825.571856"},{"key":"9209_CR10","doi-asserted-by":"crossref","first-page":"215","DOI":"10.1016\/S0304-3975(03)00085-9","volume":"304","author":"J Feigenbaum","year":"2003","unstructured":"Feigenbaum J, Krishnamurthy A, Sami R, Shenker S (2003) Hardness results for multicast cost sharing. Theor Comput Sci 304:215\u2013236","journal-title":"Theor Comput Sci"},{"key":"9209_CR11","doi-asserted-by":"crossref","first-page":"427","DOI":"10.2307\/1911219","volume":"45","author":"J Green","year":"1977","unstructured":"Green J, Laffont JJ (1977) Characterization of satisfactory mechanisms for the revelation of preferences for public goods. Econometrica 45:427\u2013438","journal-title":"Econometrica"},{"key":"9209_CR12","doi-asserted-by":"crossref","first-page":"617","DOI":"10.2307\/1914085","volume":"41","author":"T Groves","year":"1973","unstructured":"Groves T (1973) Incentives in teams. Econometrica 41:617\u2013631","journal-title":"Econometrica"},{"key":"9209_CR13","doi-asserted-by":"crossref","unstructured":"Hershberger J, Suri S (2001) Pricing in network routing: Fast payment computation. In: Proceedings of the 42nd annual IEEE symposium on foundations of computer science, pp 252\u2013259","DOI":"10.1109\/SFCS.2001.959899"},{"key":"9209_CR14","doi-asserted-by":"crossref","first-page":"847","DOI":"10.1109\/90.650144","volume":"5","author":"S Herzog","year":"1997","unstructured":"Herzog S, Shenker S, Estrin D (1997) Sharing the cost of multicast trees: An axiomatic analysis. IEEE\/ACM Trans Netw 5:847\u2013860","journal-title":"IEEE\/ACM Trans Netw"},{"key":"9209_CR15","doi-asserted-by":"crossref","unstructured":"Hoefer M (2006) Non-cooperative facility location and covering games. In: Proc 17th intl symp algorithms and computation (ISAAC), pp 369\u2013378","DOI":"10.1007\/11940128_38"},{"key":"9209_CR16","unstructured":"Immorlica N, Mahdian M, Mirrokni VS (2005) Limitations of cross-monotonic cost-sharing schemes. In: Proceedings of the 16th annual ACM-SIAM symposium on discrete algorithms (ACM SODA), pp\u00a0602\u2013611"},{"key":"9209_CR17","doi-asserted-by":"crossref","unstructured":"Jain K, Vazirani VV (2001) Applications of approximation algorithms to cooperative games. In: Proceedings of the 3rd ACM conference on electronic commerce, pp 364\u2013372","DOI":"10.1145\/380752.380825"},{"key":"9209_CR18","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1145\/585265.585266","volume":"49","author":"DJ Lehmann","year":"2002","unstructured":"Lehmann DJ, O\u0107allaghan LI, Shoham Y (2002) Truth revelation in approximately efficient combinatorial auctions. J ACM 49:577\u2013602","journal-title":"J ACM"},{"key":"9209_CR19","series-title":"LNCS","first-page":"218","volume-title":"Proceedings of the 22nd international symposium on theoretical aspects of computer science (STACS 2005)","author":"X-Y Li","year":"2005","unstructured":"Li X-Y, Sun Z, Wang W (2005) Cost sharing and strategyproof mechanisms for set cover games. In: Proceedings of the 22nd international symposium on theoretical aspects of computer science (STACS 2005), LNCS, vol\u00a03404, pp\u00a0218\u2013230. Springer, Berlin"},{"key":"9209_CR20","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1023\/A:1016770831869","volume":"17","author":"L Libman","year":"2001","unstructured":"Libman L, Orda A (2001) Atomic resource sharing in noncooperative networks. Telecommun Syst 17:385\u2013409","journal-title":"Telecommun Syst"},{"key":"9209_CR21","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1109\/TNET.2003.818196","volume":"11","author":"P Marbach","year":"2003","unstructured":"Marbach P (2003) Priority service and max-min fairness. IEEE\/ACM Trans Netw 11:733\u2013746","journal-title":"IEEE\/ACM Trans Netw"},{"key":"9209_CR22","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1007\/PL00004200","volume":"18","author":"H Moulin","year":"2001","unstructured":"Moulin H, Shenker S (2001) Strategyproof sharing of submodular costs:budget balance versus efficiency. Econ Theory 18:511\u2013533","journal-title":"Econ Theory"},{"key":"9209_CR23","doi-asserted-by":"crossref","unstructured":"Nisan N, Ronen A (1999) Algorithmic mechanism design. In: Proceedings of the 31st annual ACM symposium on theory of computing, pp\u00a0129\u2013140","DOI":"10.1145\/301250.301287"},{"key":"9209_CR24","volume-title":"A course in game theory","author":"MJ Osborne","year":"1994","unstructured":"Osborne MJ, Rubinstein A (1994) A course in game theory. MIT Press, Cambridge"},{"key":"9209_CR25","unstructured":"P\u00e1l M, Tardos E (2003) Group strategyproof mechanisms via primal-dual algorithms. In: Proceedings of the 44th annual IEEE symposium on foundations of computer science, pp 584\u2013593"},{"key":"9209_CR26","unstructured":"Penna P, Ventre C (2006) The algorithmic structure of group strategyproof budgetbalanced cost-sharing mechanisms. In: Proc of the annual symposium on theoretical aspects of computer science (STACS 3884), pp\u00a0337\u2013348"},{"key":"9209_CR27","unstructured":"Radunovi\u0107 B, Boudec J-YL (2002) A unified framework for max-min and min-max fairness with applications. In: Proceedings of 40th annual Allerton conference on communication, control, and computing"},{"key":"9209_CR28","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1145\/231699.231703","volume":"26","author":"S Shenker","year":"1996","unstructured":"Shenker S, Clark D, Estrin D, Herzog S (1996) Pricing in computer networks: Reshaping the research agenda. ACM Comput Commun Rev 26:19\u201343","journal-title":"ACM Comput Commun Rev"},{"key":"9209_CR29","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1016\/S0020-0190(97)00182-8","volume":"64","author":"P Slav\u00edk","year":"1997","unstructured":"Slav\u00edk P (1997) Improved performance of the greedy algorithm for partial cover. Inf Process Lett 64:251\u2013254","journal-title":"Inf Process Lett"},{"key":"9209_CR30","doi-asserted-by":"crossref","unstructured":"Sun Z, Li X-Y, Wang W, Chu X (2005) Mechanism design for set cover games when elements are agents. In: The first international conference on algorithmic applications in management (AAIM)","DOI":"10.1007\/11496199_39"},{"key":"9209_CR31","doi-asserted-by":"crossref","first-page":"8","DOI":"10.1111\/j.1540-6261.1961.tb02789.x","volume":"16","author":"W Vickrey","year":"1961","unstructured":"Vickrey W (1961) Counterspeculation, auctions and competitive sealed tenders. J Finance 16:8\u201337","journal-title":"J Finance"},{"key":"9209_CR32","unstructured":"Wang W, Li X-Y (2004) Truthful low-cost unicast in selfish wireless networks. In: Proceedings of the 4th international workshop on algorithms for wireless, mobile, ad hoc and sensor networks"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-009-9209-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-009-9209-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-009-9209-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,9]],"date-time":"2024-03-09T19:18:22Z","timestamp":1710011902000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-009-9209-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1,30]]},"references-count":32,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,10]]}},"alternative-id":["9209"],"URL":"https:\/\/doi.org\/10.1007\/s10878-009-9209-x","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1,30]]}}}