{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,19]],"date-time":"2025-10-19T15:46:14Z","timestamp":1760888774993},"publisher-location":"Berlin, Heidelberg","reference-count":13,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642336508"},{"type":"electronic","value":"9783642336515"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2012]]},"DOI":"10.1007\/978-3-642-33651-5_15","type":"book-chapter","created":{"date-parts":[[2012,11,13]],"date-time":"2012-11-13T09:25:32Z","timestamp":1352798732000},"page":"210-222","source":"Crossref","is-referenced-by-count":14,"title":["Distributed 2-Approximation Algorithm for the Semi-matching Problem"],"prefix":"10.1007","author":[{"given":"Andrzej","family":"Czygrinow","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michal","family":"Han\u0107kowiak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Edyta","family":"Szyma\u0144ska","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wojciech","family":"Wawrzyniak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"15_CR1","unstructured":"Andrasfai, B.: Introductory Graph Theory. Adam Hilger (1977)"},{"key":"15_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1007\/978-3-642-24100-0_18","volume-title":"Distributed Computing","author":"A. Czygrinow","year":"2011","unstructured":"Czygrinow, A., Han\u0107kowiak, M., Krzywdzi\u0144ski, K., Szyma\u0144ska, E., Wawrzyniak, W.: Brief Announcement: Distributed Approximations for the Semi-matching Problem. In: Peleg, D. (ed.) DISC 2011. LNCS, vol.\u00a06950, pp. 200\u2013201. Springer, Heidelberg (2011)"},{"key":"15_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"176","DOI":"10.1007\/978-3-642-14165-2_16","volume-title":"Automata, Languages and Programming","author":"J. Fakcharoenphol","year":"2010","unstructured":"Fakcharoenphol, J., Laekhanukit, B., Nanongkai, D.: Faster Algorithms for Semi-matching Problems (Extended Abstract). In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol.\u00a06198, pp. 176\u2013187. Springer, Heidelberg (2010)"},{"issue":"4","key":"15_CR4","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/s00453-004-1110-5","volume":"40","author":"U. Feige","year":"2004","unstructured":"Feige, U., Lovasz, L., Tetali, P.: Approximating Min Sum Set Cover. Algorithmica\u00a040(4), 219\u2013234 (2004)","journal-title":"Algorithmica"},{"key":"15_CR5","unstructured":"Han\u0107kowiak, M., Karo\u0144ski, M., Panconesi, A.: On the distributed complexity of computing maximal matchings. In: Proc. 9th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, San Francisco, CA, USA, pp. 219\u2013225 (January 1998)"},{"issue":"1","key":"15_CR6","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.jalgor.2005.01.003","volume":"59","author":"N.J.A. Harvey","year":"2006","unstructured":"Harvey, N.J.A., Ladner, R.E., Lovasz, L., Tamir, T.: Semi-matchings for bipartite graphs and load balancing, J. Algorithms\u00a059(1), 53\u201378 (2006)","journal-title":"Algorithms"},{"key":"15_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"250","DOI":"10.1007\/978-3-642-25870-1_23","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"F. Gal\u010d\u00edk","year":"2011","unstructured":"Gal\u010d\u00edk, F., Katreni\u010d, J., Semani\u0161in, G.: On Computing an Optimal Semi-matching. In: Kolman, P., Kratochv\u00edl, J. (eds.) WG 2011. LNCS, vol.\u00a06986, pp. 250\u2013261. Springer, Heidelberg (2011)"},{"issue":"1","key":"15_CR8","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N. Linial","year":"1992","unstructured":"Linial, N.: Locality in distributed graph algorithms. SIAM Journal on Computing\u00a021(1), 193\u2013201 (1992)","journal-title":"SIAM Journal on Computing"},{"issue":"2","key":"15_CR9","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1137\/080714403","volume":"39","author":"Z. Lotker","year":"2009","unstructured":"Lotker, Z., Patt-Shamir, B., Ros\u00e9n, A.: Distributed Approximate Matching. SIAM J. Comput.\u00a039(2), 445\u2013460 (2009)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"15_CR10","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/j.ipl.2006.06.004","volume":"100","author":"C.P. Low","year":"2006","unstructured":"Low, C.P.: An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs. Information Processing Letters\u00a0100(4), 154\u2013161 (2006)","journal-title":"Information Processing Letters"},{"key":"15_CR11","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed Algorithms, A Locality-Sensitive Approach. SIAM Press (2000)","DOI":"10.1137\/1.9780898719772"},{"issue":"3","key":"15_CR12","doi-asserted-by":"publisher","first-page":"341","DOI":"10.1007\/s11036-006-5187-8","volume":"11","author":"N. Sadagopan","year":"2006","unstructured":"Sadagopan, N., Singh, M., Krishnamachari, B.: Decentralized utility-based sensor network design. Mob. Netw. Appl.\u00a011(3), 341\u2013350 (2006)","journal-title":"Mob. Netw. Appl."},{"key":"15_CR13","unstructured":"Suomela, J.: Survey of Local Algorithms (manuscript), \n                    \n                      http:\/\/www.cs.helsinki.fi\/u\/josuomel\/doc\/local-survey.pdf"}],"container-title":["Lecture Notes in Computer Science","Distributed Computing"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-33651-5_15.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,4]],"date-time":"2021-05-04T12:17:28Z","timestamp":1620130648000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-33651-5_15"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012]]},"ISBN":["9783642336508","9783642336515"],"references-count":13,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-33651-5_15","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2012]]}}}