{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,7]],"date-time":"2025-07-07T08:25:00Z","timestamp":1751876700369},"publisher-location":"Berlin, Heidelberg","reference-count":17,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540651420"},{"type":"electronic","value":"9783540495437"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[1998]]},"DOI":"10.1007\/3-540-49543-6_25","type":"book-chapter","created":{"date-parts":[[2007,6,6]],"date-time":"2007-06-06T22:58:05Z","timestamp":1181170685000},"page":"319-330","source":"Crossref","is-referenced-by-count":2,"title":["Constructive Bounds and Exact Expectations for the Random Assignment Problem"],"prefix":"10.1007","author":[{"given":"Don","family":"Coppersmith","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Gregory B.","family":"Sorkin","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[1999,6,11]]},"reference":[{"key":"25_CR1","doi-asserted-by":"publisher","first-page":"507","DOI":"10.1007\/BF01192719","volume":"93","author":"D. Aldous","year":"1992","unstructured":"David Aldous. Asymptotics in the random assignment problem. Pr. Th. Related Fields, 93:507\u2013534, 1992.","journal-title":"Pr. Th. Related Fields"},{"key":"25_CR2","doi-asserted-by":"crossref","unstructured":"Don Coppersmith and Gregory B. Sorkin. Constructive bounds and exact expectations for the random assignment problem. Technical Report RC21133 (94490), IBM Reseach Report, Yorktown Heights, NY, March 1998. Accessible at http:\/\/domino.watson.ibm.com\/library\/CyberDig.nsf\/home .","DOI":"10.1007\/3-540-49543-6_25"},{"key":"25_CR3","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF01589437","volume":"35","author":"M. E. Dyer","year":"1986","unstructured":"Martin E. Dyer, Alan M. Frieze, and Colin J.H. McDiarmid. On linear programs with random costs. Mathematical Programming, 35:3\u201316, 1986.","journal-title":"Mathematical Programming"},{"issue":"4","key":"25_CR4","doi-asserted-by":"crossref","first-page":"380","DOI":"10.1147\/rd.134.0380","volume":"13","author":"W.E. Donath","year":"1969","unstructured":"W.E. Donath. Algorithm and average-value bounds for assignment problems. IBM Journal of Research and Development, 13(4):380\u2013386, July 1969.","journal-title":"IBM Journal of Research and Development"},{"key":"25_CR5","doi-asserted-by":"crossref","unstructured":"Michel X. Goemans and Muralidharan S. Kodialam. A lower bound on the expected cost of an optimal assignment. Mathematics of Operations Research, 18(2):267\u2013274, May 1993.","DOI":"10.1287\/moor.18.2.267"},{"key":"25_CR6","volume-title":"Technical report, Computer Science Division","author":"R.M. Karp","year":"1984","unstructured":"R.M. Karp. An upper bound on the expected cost of an optimal assignment. Technical report, Computer Science Division, University of California, Berkeley CA, 1984."},{"key":"25_CR7","doi-asserted-by":"crossref","unstructured":"Richard M. Karp. An upper bound on the expected cost of an optimal assignment. In David S. Johnson et al., editors, Discrete Algorithms and Complexity: Proceedings of the Japan-US Joint Seminar, volume 15 of Perspectives in Computing, pages 1\u20134. Academic Press, 1987.","DOI":"10.1016\/B978-0-12-386870-1.50006-X"},{"key":"25_CR8","doi-asserted-by":"crossref","unstructured":"Richard M. Karp, Alexander H.G. Rinnooy Kan, and Rakesh V. Vohra. Average case analysis of a heuristic for the assignment problem. Mathematics of Operations Research, 19(3):513\u2013522, August 1994.","DOI":"10.1287\/moor.19.3.513"},{"key":"25_CR9","volume-title":"Master\u2019s thesis","author":"A. J. Lazarus","year":"1979","unstructured":"Andrew J. Lazarus. The assignment problem with uniform (0,1) cost matrix. Master\u2019s thesis, Department of Mathematics, Princeton University, Princeton, N.J., 1979."},{"issue":"4","key":"25_CR10","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1016\/0167-6377(93)90071-N","volume":"14","author":"A. J. Lazarus","year":"1993","unstructured":"Andrew J. Lazarus. Certain expected values in the random assignment problem. Oper. Res. Lett., 14(4):207\u2013214, 1993.","journal-title":"Oper. Res. Lett."},{"key":"25_CR11","first-page":"148","volume":"141","author":"C. McDiarmid","year":"1989","unstructured":"Colin McDiarmid. On the method of bounded differences. In London Mathematical Society Lecture Note Series, volume 141, pages 148\u2013188. Cambridge University Press, 1989.","journal-title":"London Mathematical Society Lecture Note Series"},{"key":"25_CR12","doi-asserted-by":"crossref","unstructured":"M. M\u00e9zard and G. Parisi. Replicas and optimization. J. Physique Lettres, 46:771\u2013778, September 1985.","DOI":"10.1051\/jphyslet:019850046017077100"},{"key":"25_CR13","doi-asserted-by":"crossref","first-page":"1451","DOI":"10.1051\/jphys:019870048090145100","volume":"48","author":"M. M\u00e9zard","year":"1987","unstructured":"M. M\u00e9zard and G. Parisi. On the solution of the random link matching problems. J. Physique Lettres, 48:1451\u20131459, September 1987.","journal-title":"J. Physique Lettres"},{"key":"25_CR14","series-title":"PhD thesis","volume-title":"Asymptotic Properties of Random Assignment Problems","author":"B. Olin","year":"1992","unstructured":"Birgitta Olin. Asymptotic Properties of Random Assignment Problems. PhD thesis, Kungl Tekniska H\u00f6gskolan, Stockholm, Sweden, 1992."},{"key":"25_CR15","unstructured":"Giorgio Parisi. A conjecture on random bipartite matching. Physics e-Print archive, http:\/\/xxx.lanl.gov\/ps\/-cond-mat\/9801176 , January 1998."},{"key":"25_CR16","doi-asserted-by":"crossref","unstructured":"Boris Pittel and Robert S. Weishaar. The random bipartite nearest neighbor graphs. Submitted for publication, 1998.","DOI":"10.1002\/(SICI)1098-2418(199910\/12)15:3\/4<279::AID-RSA6>3.3.CO;2-A"},{"key":"25_CR17","doi-asserted-by":"crossref","unstructured":"David W. Walkup. On the expected value of a random assignment problem. SIAM J. Computing, 8(3):440\u2013442, August 1979.","DOI":"10.1137\/0208036"}],"container-title":["Lecture Notes in Computer Science","Randomization and Approximation Techniques in Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-49543-6_25","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,28]],"date-time":"2019-04-28T15:46:00Z","timestamp":1556466360000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-49543-6_25"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998]]},"ISBN":["9783540651420","9783540495437"],"references-count":17,"URL":"https:\/\/doi.org\/10.1007\/3-540-49543-6_25","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[1998]]}}}