{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,4]],"date-time":"2024-09-04T12:43:25Z","timestamp":1725453805202},"publisher-location":"Berlin, Heidelberg","reference-count":10,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642387678"},{"type":"electronic","value":"9783642387685"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-38768-5_63","type":"book-chapter","created":{"date-parts":[[2013,5,17]],"date-time":"2013-05-17T04:31:28Z","timestamp":1368765088000},"page":"705-712","source":"Crossref","is-referenced-by-count":0,"title":["Perturbation Analysis of Maximum-Weighted Bipartite Matchings with Low Rank Data"],"prefix":"10.1007","author":[{"given":"Xingwu","family":"Liu","sequence":"first","affiliation":[]},{"given":"Shang-Hua","family":"Teng","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"5","key":"63_CR1","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S. Arora","year":"1998","unstructured":"Arora, S.: Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. J. ACM\u00a045(5), 753\u2013782 (1998)","journal-title":"J. ACM"},{"key":"63_CR2","unstructured":"Ball, K.: An elementary introduction to modern convex geometry. In: Flavors of Geometry, pp. 1\u201358. Univ. Press (1997)"},{"key":"63_CR3","doi-asserted-by":"crossref","unstructured":"Duan, R., Pettie, S.: Approximating maximum weight matching in near-linear time. In: Proceedings of the 2010 IEEE 51st Annual Symposium on Foundations of Computer Science, pp. 673\u2013682 (2010)","DOI":"10.1109\/FOCS.2010.70"},{"key":"63_CR4","doi-asserted-by":"crossref","unstructured":"Gr\u00f6etschel, M., Lov\u00e1sz, L., Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. Springer (1988)","DOI":"10.1007\/978-3-642-97881-4"},{"key":"63_CR5","unstructured":"Karger, D.: Personal communication (2009)"},{"issue":"4","key":"63_CR6","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1137\/S0097539796309764","volume":"28","author":"J.S.B. Mitchell","year":"1999","unstructured":"Mitchell, J.S.B.: Guillotine subdivisions approximate polygonal subdivisions: A simple polynomial-time approximation scheme for geometric tsp, k-mst, and related problems. SIAM J. Comput.\u00a028(4), 1298\u20131309 (1999)","journal-title":"SIAM J. Comput."},{"key":"63_CR7","unstructured":"Papadimitriou, C.H., Steiglitz, K.: Combinatorial optimization: algorithms and complexity. Prentice-Hall, Inc. (1982)"},{"key":"63_CR8","doi-asserted-by":"crossref","unstructured":"Sharathkumar, R., Agarwal, P.K.: A near-linear time ε-approximation algorithm for geometric bipartite matching. In: Proceedings of the 44th Symposium on Theory of Computing, pp. 385\u2013394 (2012)","DOI":"10.1145\/2213977.2214014"},{"key":"63_CR9","doi-asserted-by":"crossref","unstructured":"Vaidya, P.: Geometry helps in matching. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pp. 422\u2013425 (1988)","DOI":"10.1145\/62212.62253"},{"issue":"4","key":"63_CR10","doi-asserted-by":"publisher","first-page":"569","DOI":"10.1007\/BF01553909","volume":"4","author":"P.M. Vaidya","year":"1989","unstructured":"Vaidya, P.M.: Approximate minimum weight matching on points in k-dimensional space. Algorithmica\u00a04(4), 569\u2013583 (1989)","journal-title":"Algorithmica"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-38768-5_63","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,13]],"date-time":"2019-05-13T02:08:23Z","timestamp":1557713303000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-38768-5_63"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642387678","9783642387685"],"references-count":10,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-38768-5_63","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2013]]}}}