{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T19:55:16Z","timestamp":1760298916163,"version":"3.40.4"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2014,4,23]],"date-time":"2014-04-23T00:00:00Z","timestamp":1398211200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2015,8]]},"DOI":"10.1007\/s10107-014-0781-1","type":"journal-article","created":{"date-parts":[[2014,4,22]],"date-time":"2014-04-22T13:04:14Z","timestamp":1398171854000},"page":"147-188","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Efficient cost-sharing mechanisms for prize-collecting problems"],"prefix":"10.1007","volume":"152","author":[{"given":"A.","family":"Gupta","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"J.","family":"K\u00f6nemann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S.","family":"Leonardi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R.","family":"Ravi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G.","family":"Sch\u00e4fer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,4,23]]},"reference":[{"issue":"3","key":"781_CR1","doi-asserted-by":"crossref","first-page":"440","DOI":"10.1137\/S0097539792236237","volume":"24","author":"A Agrawal","year":"1995","unstructured":"Agrawal, A., Klein, P., Ravi, R.: When trees collide: an approximation algorithm for the generalized Steiner problem on networks. SIAM J. Comput. 24(3), 440\u2013456 (1995)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"781_CR2","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1137\/090771429","volume":"40","author":"A Archer","year":"2011","unstructured":"Archer, A., Bateni, M., Hajiaghayi, M., Karloff, H.: Improved approximation algorithms for prize-collecting steiner tree and TSP. SIAM J. Comput. 40(2), 309\u2013332 (2011)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"781_CR3","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.: Approximation and collusion in multicast cost sharing. Games Econ. Behav. 47(1), 36\u201371 (2004)","journal-title":"Games Econ. Behav."},{"issue":"3","key":"781_CR4","doi-asserted-by":"crossref","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and the hardness of approximation problems. J. ACM 45(3), 501\u2013555 (1998)","journal-title":"J. ACM"},{"key":"781_CR5","doi-asserted-by":"crossref","unstructured":"Bartal, Y.: Probabilistic approximations of metric spaces and its algorithmic applications. In: Proceedings of the 37th Symposium on the Foundations of Computer, Science, pp. 184\u2013193 (1996)","DOI":"10.1109\/SFCS.1996.548477"},{"key":"781_CR6","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/0020-0190(89)90039-2","volume":"32","author":"M Bern","year":"1989","unstructured":"Bern, M., Plassman, P.: The Steiner problem with edge lengths 1 and 2. Inf. Process. Lett. 32, 171\u2013176 (1989)","journal-title":"Inf. Process. Lett."},{"key":"781_CR7","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1007\/BF01581256","volume":"59","author":"D Bienstock","year":"1993","unstructured":"Bienstock, D., Goemans, M.X., Simchi-Levi, D., Williamson, D.P.: A note on the prize collecting traveling salesman problem. Math. Program. 59, 413\u2013420 (1993)","journal-title":"Math. Program."},{"issue":"3","key":"781_CR8","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1016\/j.jda.2009.02.001","volume":"7","author":"Y Bleischwitz","year":"2009","unstructured":"Bleischwitz, Y., Monien, B.: Fair cost-sharing methods for scheduling jobs on parallel machines. J. Discrete Algorithms 7(3), 280\u2013290 (2009)","journal-title":"J. Discrete Algorithms"},{"key":"781_CR9","doi-asserted-by":"crossref","unstructured":"Bleischwitz, Y., Monien, B., Schoppmann, F.: To be or not to be (served). In: Proceedings of the 3rd International Conference on Internet and Network Economics, pp. 515\u2013528 (2007)","DOI":"10.1007\/978-3-540-77105-0_55"},{"key":"781_CR10","doi-asserted-by":"crossref","unstructured":"Brenner, J., Sch\u00e4fer, G.: Cost sharing methods for makespan and completion time scheduling. In: Proceedings of the 24th International Symposium on Theoretical Aspects of Computer, Science, pp. 670\u2013681 (2007)","DOI":"10.1007\/978-3-540-70918-3_57"},{"key":"781_CR11","doi-asserted-by":"crossref","unstructured":"Chawla, S., Roughgarden, T., Sundararajan, M.: Optimal cost-sharing mechanisms for steiner forest problems. In: Proceedings of the 2nd International Workshop on Internet and Network Economics, pp. 112\u2013123 (2006)","DOI":"10.1007\/11944874_11"},{"issue":"3","key":"781_CR12","doi-asserted-by":"crossref","first-page":"615","DOI":"10.2307\/1911055","volume":"57","author":"B Dutta","year":"1989","unstructured":"Dutta, B., Ray, D.: A concept of egalitarianism under participation constraints. Econometrica 57(3), 615\u2013635 (1989)","journal-title":"Econometrica"},{"issue":"3","key":"781_CR13","doi-asserted-by":"crossref","first-page":"485","DOI":"10.1016\/j.jcss.2004.04.011","volume":"69","author":"J Fakcharoenphol","year":"2004","unstructured":"Fakcharoenphol, J., Rao, S., Talwar, K.: A tight bound on approximating arbitrary metrics by tree metrics. J. Comput. Syst. Sci. 69(3), 485\u2013497 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"781_CR14","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.: Hardness results for multicast cost-sharing. Theor. Comput. Sci. 304, 215\u2013236 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"1","key":"781_CR15","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1006\/jcss.2001.1754","volume":"63","author":"J Feigenbaum","year":"2001","unstructured":"Feigenbaum, J., Papadimitriou, C.H., Shenker, S.: Sharing the cost of multicast transmissions. J. Comput. Syst. Sci. 63(1), 21\u201341 (2001)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"781_CR16","doi-asserted-by":"crossref","first-page":"296","DOI":"10.1137\/S0097539793242618","volume":"24","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: A general approximation technique for constrained forest problems. SIAM J. Comput. 24(2), 296\u2013317 (1995)","journal-title":"SIAM J. Comput."},{"key":"781_CR17","doi-asserted-by":"crossref","first-page":"375","DOI":"10.1016\/0047-2727(76)90049-9","volume":"6","author":"J Green","year":"1976","unstructured":"Green, J., Kohlberg, E., Laffont, J.J.: Partial equilibrium approach to the free rider problem. J. Public Econ. 6, 375\u2013394 (1976)","journal-title":"J. Public Econ."},{"issue":"1","key":"781_CR18","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1007\/s00453-007-9065-y","volume":"50","author":"A Gupta","year":"2008","unstructured":"Gupta, A., Srinivasan, A., Tardos, \u00c9.: Cost-sharing mechanisms for network design. Algorithmica 50(1), 98\u2013119 (2008)","journal-title":"Algorithmica"},{"key":"781_CR19","doi-asserted-by":"crossref","unstructured":"Hajiaghayi, M.T., Jain, K.: The prize-collecting generalized Steiner tree problem via a new approach of primal-dual schema. In: Proceedings of the 17th Annual ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 631\u2013640 (2006)","DOI":"10.1145\/1109557.1109626"},{"key":"781_CR20","unstructured":"Immorlica, N., Mahdian, M., Mirrokni, V.S.: Limitations of cross-monotonic cost sharing schemes. In: Proceedings of the 16th Annual ACM\u2013SIAM Symposium on Discrete Algorithms, pp. 602\u2013611 (2005)"},{"issue":"4","key":"781_CR21","doi-asserted-by":"crossref","first-page":"761","DOI":"10.1145\/502090.502096","volume":"48","author":"S Iwata","year":"2001","unstructured":"Iwata, S., Fleischer, L., Fujishige, S.: A combinatorial strongly polynomial algorithm for minimizing submodular functions. J. ACM 48(4), 761\u2013777 (2001)","journal-title":"J. ACM"},{"key":"781_CR22","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, pp. 364\u2013372 (2001)","DOI":"10.1145\/380752.380825"},{"key":"781_CR23","doi-asserted-by":"crossref","unstructured":"Jain, K., Vazirani, V.V.: Equitable cost allocations via primal-dual-type algorithms. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing, pp. 313\u2014321 (2002)","DOI":"10.1145\/509907.509956"},{"key":"781_CR24","unstructured":"Kent, K.J., Skorin-Kapov, D.: Population monotonic cost allocations on MSTs. In: Proceedings of the 6th International Conference on Operational Research, pp. 43\u201348 (1996)"},{"key":"781_CR25","doi-asserted-by":"crossref","unstructured":"K\u00f6nemann, J., Leonardi, S., Sch\u00e4fer, G., van Zwam, S.: From primal-dual to cost shares and back: a stronger LP relaxation for the Steiner forest problem. In: Proceedings of the 32nd International Colloquium on Automata, Languages and Programming, pp. 930\u2013942 (2005)","DOI":"10.1007\/11523468_75"},{"issue":"5","key":"781_CR26","doi-asserted-by":"crossref","first-page":"1319","DOI":"10.1137\/050646408","volume":"37","author":"J K\u00f6nemann","year":"2008","unstructured":"K\u00f6nemann, J., Leonardi, S., Sch\u00e4fer, G., van Zwam, S.H.M.: A group-strategyproof cost sharing mechanism for the Steiner forest game. SIAM J. Comput. 37(5), 1319\u20131341 (2008)","journal-title":"SIAM J. Comput."},{"issue":"1\u20133","key":"781_CR27","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. Theoret. Comput. Sci. 326(1\u20133), 431\u2013442 (2004)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"781_CR28","doi-asserted-by":"crossref","first-page":"816","DOI":"10.1137\/S0097539701383443","volume":"32","author":"RR Mettu","year":"2003","unstructured":"Mettu, R.R., Plaxton, C.G.: The online median problem. SIAM J. Comput. 32(3), 816\u2013832 (2003)","journal-title":"SIAM J. Comput."},{"key":"781_CR29","doi-asserted-by":"crossref","first-page":"279","DOI":"10.1007\/s003550050145","volume":"16","author":"H Moulin","year":"1999","unstructured":"Moulin, H.: Incremental cost sharing: characterization by coalition strategy-proofness. Soc. Choice Welfare 16, 279\u2013320 (1999)","journal-title":"Soc. Choice Welfare"},{"issue":"3","key":"781_CR30","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. Theor. 18(3), 511\u2013533 (2001)","journal-title":"Econ. Theor."},{"key":"781_CR31","doi-asserted-by":"crossref","unstructured":"Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V.V. (eds.).: Algorithmic Game Theory. Cambridge University Press, Cambridge (2007)","DOI":"10.1017\/CBO9780511800481"},{"key":"781_CR32","doi-asserted-by":"crossref","unstructured":"P\u00e1l, M., Tardos, E.: Group strategyproof mechanisms via primal-dual algorithms. In: Proceedings of the 44th Symposium on the Foundations of Computer, Science, pp. 584\u2013593 (2003)","DOI":"10.1109\/SFCS.2003.1238231"},{"key":"781_CR33","doi-asserted-by":"crossref","unstructured":"Pountourakis, E., Vidali, A.: A complete characterization of group-strategyproof mechanisms of cost-sharing. In: Proceedings of the 18th Annual European Symposium on Algorithms, pp. 146\u2013157 (2010)","DOI":"10.1007\/978-3-642-15775-2_13"},{"key":"781_CR34","volume-title":"Aggregation and Revelation of Preferences","author":"K Roberts","year":"1979","unstructured":"Roberts, K.: The characterization of implementable choice rules. In: Laffont, J.J. (ed.) Aggregation and Revelation of Preferences. North-Holland, Amsterdam (1979)"},{"key":"781_CR35","doi-asserted-by":"crossref","unstructured":"Roughgarden, T., Sundararajan, M.: Optimal efficiency guarantees for network design mechanisms. In: Proceedings of the 12th International Conference on Integer Programming and Combinatorial Optimization, pp. 469\u2013483 (2007)","DOI":"10.1007\/978-3-540-72792-7_35"},{"key":"781_CR36","doi-asserted-by":"crossref","unstructured":"Roughgarden, T., Sundararajan, M.: Quantifying inefficiency in cost-sharing mechanisms. J. ACM 56(4), 1\u201333 (2009)","DOI":"10.1145\/1538902.1538907"},{"issue":"2","key":"781_CR37","doi-asserted-by":"crossref","first-page":"346","DOI":"10.1006\/jctb.2000.1989","volume":"80","author":"A Schrijver","year":"2000","unstructured":"Schrijver, A.: A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Comb. Theory Ser. B 80(2), 346\u2013355 (2000)","journal-title":"J. Comb. Theory Ser. B"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-014-0781-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-014-0781-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-014-0781-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,2]],"date-time":"2025-05-02T14:18:08Z","timestamp":1746195488000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-014-0781-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,4,23]]},"references-count":37,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2015,8]]}},"alternative-id":["781"],"URL":"https:\/\/doi.org\/10.1007\/s10107-014-0781-1","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2014,4,23]]}}}