{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,19]],"date-time":"2025-10-19T05:55:23Z","timestamp":1760853323133,"version":"3.33.0"},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2007,10,17]],"date-time":"2007-10-17T00:00:00Z","timestamp":1192579200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2008,1]]},"DOI":"10.1007\/s00453-007-9065-y","type":"journal-article","created":{"date-parts":[[2007,10,16]],"date-time":"2007-10-16T14:50:21Z","timestamp":1192546221000},"page":"98-119","source":"Crossref","is-referenced-by-count":18,"title":["Cost-Sharing Mechanisms for Network Design"],"prefix":"10.1007","volume":"50","author":[{"given":"Anupam","family":"Gupta","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Aravind","family":"Srinivasan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"\u00c9va","family":"Tardos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2007,10,17]]},"reference":[{"key":"9065_CR1","doi-asserted-by":"crossref","first-page":"567","DOI":"10.1016\/0196-6774(86)90019-2","volume":"7","author":"N. Alon","year":"1986","unstructured":"Alon, N., Babai, L., Itai, A.: A fast and simple randomized parallel algorithm for the maximal independent set problem. J. Algorithms 7, 567\u2013583 (1986)","journal-title":"J. Algorithms"},{"key":"9065_CR2","doi-asserted-by":"crossref","unstructured":"Bellare, M., Rompel, J.: Randomness-efficient oblivious sampling. In: Proceedings of the IEEE Symposium on Foundations of Computer Science, pp.\u00a0276\u2013287 (1994)","DOI":"10.1109\/SFCS.1994.365687"},{"key":"9065_CR3","doi-asserted-by":"crossref","unstructured":"Even, G., Goldreich, O., Luby, M., Nisan, N., Boban, V.: Approximations of general independent distributions. In: Proceedings of the 24th Annual ACM Symposium on Theory of Computing, pp.\u00a010\u201316 (1992)","DOI":"10.1145\/129712.129714"},{"key":"9065_CR4","doi-asserted-by":"crossref","unstructured":"Gupta, A., Kumar, A., Roughgarden, T.: Simpler and better approximation algorithms for network design. In: Proceedings of the 35th Annual ACM Symposium on Theory of Computing, pp.\u00a0365\u2013372 (2003)","DOI":"10.1145\/780542.780597"},{"key":"9065_CR5","first-page":"43","volume-title":"Proceedings of the 6th International Conference on Operational Research","author":"K.J. Kent","year":"1996","unstructured":"Kent, K.J., Skorin-Kapov, D.: Population monotonic cost allocations on MSTs. In: Proceedings of the 6th International Conference on Operational Research, Rovinj, pp.\u00a043\u201348. Croatian Oper. Res. Soc., Zagreb (1996)"},{"issue":"4","key":"9065_CR6","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M. Luby","year":"1986","unstructured":"Luby, M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15(4), 1036\u20131053 (1986)","journal-title":"SIAM J. Comput."},{"key":"9065_CR7","doi-asserted-by":"crossref","first-page":"511","DOI":"10.1007\/PL00004200","volume":"18","author":"H. Moulin","year":"2001","unstructured":"Moulin, H., Shenker, S.: Strategyproof sharing of submodular costs: budget balance versus efficiency. Econ. Theory 18, 511\u2013533 (2001)","journal-title":"Econ. Theory"},{"key":"9065_CR8","doi-asserted-by":"crossref","unstructured":"Jain, K., Vazirani, V.: Applications of approximation algorithms to cooperative games. In: Proceedings of the 33rd Annual ACM Symposium on the Theory of Computing (STOC), pp.\u00a0364\u2013372 (2001)","DOI":"10.1145\/380752.380825"},{"issue":"1\u20133","key":"9065_CR9","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1016\/j.tcs.2004.07.033","volume":"326","author":"S. Leonardi","year":"2004","unstructured":"Leonardi, S., Sch\u00e4fer, G.: Cross-monotonic cost-sharing methods for connected facility location games. Theor. Comput. Sci. 326(1\u20133), 431\u2013442 (2004)","journal-title":"Theor. Comput. Sci."},{"key":"9065_CR10","series-title":"Lecture Notes in Comput. Sci.","doi-asserted-by":"crossref","first-page":"229","DOI":"10.1007\/3-540-45753-4_20","volume-title":"Approximation Algorithms for Combinatorial Optimization","author":"M. Mahdian","year":"2002","unstructured":"Mahdian, M., Ye, Y., Zhang, J.: Improved approximation algorithms for metric facility location problems. In: Approximation Algorithms for Combinatorial Optimization. Lecture Notes in Comput. Sci., vol.\u00a02462, pp.\u00a0229\u2013242. Springer, Berlin (2002)"},{"key":"9065_CR11","doi-asserted-by":"crossref","unstructured":"P\u00e1l, M., Tardos, \u00c9.: Group strategyproof mechanisms via primal-dual algorithms. In: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, pp.\u00a0584\u2013593 (2003)","DOI":"10.1109\/SFCS.2003.1238231"},{"key":"9065_CR12","unstructured":"Robins, G., Zelikovsky, A.: Improved Steiner tree approximation in graphs. In: Proceedings of the 11th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.\u00a0770\u2013779 (2000)"},{"key":"9065_CR13","doi-asserted-by":"crossref","first-page":"223","DOI":"10.1137\/S089548019223872X","volume":"8","author":"J.P. Schmidt","year":"1995","unstructured":"Schmidt, J.P., Siegel, A., Srinivasan, A.: Chernoff\u2013Hoeffding bounds for applications with limited independence. SIAM J. Discrete Math. 8, 223\u2013250 (1995)","journal-title":"SIAM J. Discrete Math."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9065-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-007-9065-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-007-9065-y","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T18:02:19Z","timestamp":1737482539000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-007-9065-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,10,17]]},"references-count":13,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,1]]}},"alternative-id":["9065"],"URL":"https:\/\/doi.org\/10.1007\/s00453-007-9065-y","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2007,10,17]]}}}