{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T11:41:09Z","timestamp":1725536469769},"publisher-location":"Berlin, Heidelberg","reference-count":27,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642036842"},{"type":"electronic","value":"9783642036859"}],"license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2009]]},"DOI":"10.1007\/978-3-642-03685-9_33","type":"book-chapter","created":{"date-parts":[[2009,8,20]],"date-time":"2009-08-20T22:39:51Z","timestamp":1250807991000},"page":"434-447","source":"Crossref","is-referenced-by-count":2,"title":["Average-Case Analyses of Vickrey Costs"],"prefix":"10.1007","author":[{"given":"Prasad","family":"Chebolu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alan","family":"Frieze","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"P\u00e1ll","family":"Melsted","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gregory B.","family":"Sorkin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"33_CR1","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1214\/aoap\/1177005773","volume":"2","author":"F. Avram","year":"1992","unstructured":"Avram, F., Bertsimas, D.: The minimum spanning tree constant in geometrical probability and under the independent model: a unified approach. Annals of Applied Probability\u00a02, 113\u2013130 (1992)","journal-title":"Annals of Applied Probability"},{"key":"33_CR2","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1007\/BF01192719","volume":"93","author":"D. Aldous","year":"1992","unstructured":"Aldous, D.: Asymptotics in the random assignment problem. Pr. Th. Related Fields\u00a093, 507\u2013534 (1992)","journal-title":"Pr. Th. Related Fields"},{"issue":"4","key":"33_CR3","doi-asserted-by":"publisher","first-page":"381","DOI":"10.1002\/rsa.1015","volume":"18","author":"D.J. Aldous","year":"2001","unstructured":"Aldous, D.J.: The \u03b6(2) limit in the random assignment problem. Random Structures Algorithms\u00a018(4), 381\u2013418 (2001)","journal-title":"Random Structures Algorithms"},{"key":"33_CR4","unstructured":"Archer, A., Tardos, \u00c9.: Frugal path mechanisms. In: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, San Francisco, California, January 06-08, 2002, pp. 991\u2013999 (2002)"},{"issue":"1","key":"33_CR5","doi-asserted-by":"publisher","first-page":"22","DOI":"10.1145\/1186810.1186813","volume":"3","author":"A. Archer","year":"2007","unstructured":"Archer, A., Tardos, \u00c9.: Frugal path mechanisms. ACM Trans. Algorithms\u00a03(1), Art. 3, 22 (2007); MRMR2301829 (2008b:68013)","journal-title":"ACM Trans. Algorithms"},{"key":"33_CR6","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1007\/BF01726210","volume":"8","author":"E.H. Clarke","year":"1971","unstructured":"Clarke, E.H.: Multipart pricing of public goods. Public Choice\u00a08, 17\u201333 (1971)","journal-title":"Public Choice"},{"key":"33_CR7","doi-asserted-by":"crossref","unstructured":"Czumaj, A., Ronen, A.: On the expected payment of mechanisms for task allocation (extended abstract). In: Proceedings of the Fifth ACM Conference on Electronic Commerce, pp. 252\u2013253 (2004)","DOI":"10.1145\/988772.988819"},{"issue":"2","key":"33_CR8","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1002\/(SICI)1098-2418(199909)15:2<113::AID-RSA1>3.0.CO;2-S","volume":"15","author":"D. Coppersmith","year":"1999","unstructured":"Coppersmith, D., Sorkin, G.B.: Constructive bounds and exact expectations for the random assignment problem. Random Structures Algorithms\u00a015(2), 113\u2013144 (1999); MR2001j:05096","journal-title":"Random Structures Algorithms"},{"key":"33_CR9","doi-asserted-by":"crossref","unstructured":"Elkind, E.: True costs of cheap labor are hard to measure: edge deletion and VCG payments in graphs. In: Proceedings of the Sixth ACM Conference on Electronic Commerce, pp. 108\u2013117 (2005)","DOI":"10.1145\/1064009.1064021"},{"key":"33_CR10","unstructured":"Elkind, E., Sahai, A., Steiglitz, K.: Frugality in path auctions. In: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 694\u2013702 (2004)"},{"key":"33_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1007\/11944874_10","volume-title":"Internet and Network Economics","author":"A. Flaxman","year":"2006","unstructured":"Flaxman, A., Gamarnik, D., Sorkin, G.B.: First-passage percolation on a width-2 strip and the path cost in a VCG auction. In: Spirakis, P.G., Mavronicolas, M., Kontogiannis, S.C. (eds.) WINE 2006. LNCS, vol.\u00a04286, pp. 99\u2013111. Springer, Heidelberg (2006)"},{"key":"33_CR12","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1145\/571825.571856","volume-title":"PODC 2002: Proceedings of the Twenty-First Annual Symposium on Principles of Distributed Computing","author":"J. Feigenbaum","year":"2002","unstructured":"Feigenbaum, J., Papadimitriou, C., Sami, R., Shenker, S.: A BGP-based mechanism for lowest-cost routing. In: PODC 2002: Proceedings of the Twenty-First Annual Symposium on Principles of Distributed Computing, pp. 173\u2013182. ACM Press, New York (2002)"},{"key":"33_CR13","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0166-218X(85)90058-7","volume":"10","author":"A. Frieze","year":"1985","unstructured":"Frieze, A.: On the value of a random minimum spanning tree problem. Discrete Applied Mathematics\u00a010, 47\u201356 (1985)","journal-title":"Discrete Applied Mathematics"},{"issue":"4","key":"33_CR14","doi-asserted-by":"publisher","first-page":"617","DOI":"10.2307\/1914085","volume":"41","author":"T. Groves","year":"1973","unstructured":"Groves, T.: Incentives in teams. Econometrica\u00a041(4), 617\u2013631 (1973)","journal-title":"Econometrica"},{"key":"33_CR15","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1017\/S0963548399003892","volume":"8","author":"S. Janson","year":"1999","unstructured":"Janson, S.: One, two, three logn\/n for paths in a complete graph with random weights. Combinatorics, Probability and Computing\u00a08, 347\u2013361 (1999)","journal-title":"Combinatorics, Probability and Computing"},{"key":"33_CR16","first-page":"126","volume-title":"PODC 2005: Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing","author":"D. Karger","year":"2005","unstructured":"Karger, D., Nikolova, E.: Brief announcement: on the expected overpayment of VCG mechanisms in large networks. In: PODC 2005: Proceedings of the 24th Annual ACM Symposium on Principles of Distributed Computing, pp. 126\u2013126. ACM Press, New York (2005)"},{"key":"33_CR17","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/s00440-003-0308-9","volume":"128","author":"S. Linusson","year":"2004","unstructured":"Linusson, S., W\u00e4stlund, J.: A proof of Parisi\u2019s conjecture on the random assignment problem. Probability Theory and Related Fields\u00a0128, 419\u2013440 (2004)","journal-title":"Probability Theory and Related Fields"},{"key":"33_CR18","doi-asserted-by":"publisher","first-page":"771","DOI":"10.1051\/jphyslet:019850046017077100","volume":"46","author":"M. M\u00e9zard","year":"1985","unstructured":"M\u00e9zard, M., Parisi, G.: Replicas and optimization. J. Physique Lettres\u00a046, 771\u2013778 (1985)","journal-title":"J. Physique Lettres"},{"key":"33_CR19","doi-asserted-by":"publisher","first-page":"913","DOI":"10.1209\/0295-5075\/2\/12\/005","volume":"2","author":"M. M\u00e9zard","year":"1986","unstructured":"M\u00e9zard, M., Parisi, G.: Mean-field equations for the matching and the travelling salesman problems. Europhys. Lett.\u00a02, 913\u2013918 (1986)","journal-title":"Europhys. Lett."},{"key":"33_CR20","doi-asserted-by":"publisher","first-page":"1451","DOI":"10.1051\/jphys:019870048090145100","volume":"48","author":"M. M\u00e9zard","year":"1987","unstructured":"M\u00e9zard, M., Parisi, G.: On the solution of the random link matching problems. J. Physique Lettres\u00a048, 1451\u20131459 (1987)","journal-title":"J. Physique Lettres"},{"key":"33_CR21","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1109\/SFCS.2003.1238178","volume-title":"FOCS 2003: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science","author":"M. Mihail","year":"2003","unstructured":"Mihail, M., Papadimitriou, C., Saberi, A.: On certain connectivity properties of the Internet topology. In: FOCS 2003: Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science, Washington, DC, USA, p. 28. IEEE Computer Society Press, Los Alamitos (2003)"},{"issue":"4","key":"33_CR22","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1002\/rsa.20084","volume":"27","author":"C. Nair","year":"2005","unstructured":"Nair, C., Prabhakar, B., Sharma, M.: Proofs of the Parisi and Coppersmith-Sorkin random assignment conjectures. Random Structures Algorithms\u00a027(4), 413\u2013444 (2005) MR MR2178256 (2006e:90050)","journal-title":"Random Structures Algorithms"},{"key":"33_CR23","doi-asserted-by":"crossref","unstructured":"Nisan, N., Ronen, A.: Algorithmic mechanism design (extended abstract). In: Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, Atlanta, Georgia, United States, pp. 129\u2013140 (1999)","DOI":"10.1145\/301250.301287"},{"issue":"1-2","key":"33_CR24","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1006\/game.1999.0790","volume":"35","author":"N. Nisan","year":"2001","unstructured":"Nisan, N., Ronen, A.: Algorithmic mechanism design. Games Econom. Behav.\u00a035(1-2), 166\u2013196 (2001); Economics and artificial intelligence MR MR1822468 (2002a:68146)","journal-title":"Games Econom. Behav."},{"key":"33_CR25","unstructured":"Parisi, G.: A conjecture on random bipartite matching, Physics e-Print archive (January 1998), \n                    \n                      http:\/\/xxx.lanl.gov\/ps\/cond-mat\/9801176"},{"key":"33_CR26","doi-asserted-by":"publisher","first-page":"8","DOI":"10.1111\/j.1540-6261.1961.tb02789.x","volume":"16","author":"W. Vickrey","year":"1961","unstructured":"Vickrey, W.: Counterspeculation, auctions and competitive sealed tenders. Journal of Finance\u00a016, 8\u201337 (1961)","journal-title":"Journal of Finance"},{"key":"33_CR27","unstructured":"W\u00e4stlund, J.: An easy proof of the zeta(2) limit in the random assignment problem. Electronic Journal of Probability (to appear)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-03685-9_33","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,19]],"date-time":"2019-05-19T12:15:22Z","timestamp":1558268122000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-03685-9_33"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009]]},"ISBN":["9783642036842","9783642036859"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-03685-9_33","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2009]]}}}