{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:02Z","timestamp":1740109262877,"version":"3.37.3"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2017,6,3]],"date-time":"2017-06-03T00:00:00Z","timestamp":1496448000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Icelandic Research Fund","award":["120032011","152679-051"],"award-info":[{"award-number":["120032011","152679-051"]}]},{"name":"Sustainability Center Freiburg"},{"DOI":"10.13039\/501100001738","name":"Ministry of Science, Technology and Space","doi-asserted-by":"publisher","award":["3-10996"],"award-info":[{"award-number":["3-10996"]}],"id":[{"id":"10.13039\/501100001738","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1444\/14"],"award-info":[{"award-number":["1444\/14"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001738","name":"Ministry of Science, Technology and Space","doi-asserted-by":"publisher","award":["3-10996"],"award-info":[{"award-number":["3-10996"]}],"id":[{"id":"10.13039\/501100001738","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["497\/14"],"award-info":[{"award-number":["497\/14"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2018,4]]},"DOI":"10.1007\/s00446-017-0299-x","type":"journal-article","created":{"date-parts":[[2017,6,3]],"date-time":"2017-06-03T09:19:36Z","timestamp":1496481576000},"page":"83-98","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Distributed backup placement in networks"],"prefix":"10.1007","volume":"31","author":[{"given":"Magn\u00fas M.","family":"Halld\u00f3rsson","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6068-135X","authenticated-orcid":false,"given":"Sven","family":"K\u00f6hler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Boaz","family":"Patt-Shamir","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dror","family":"Rawitz","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,6,3]]},"reference":[{"issue":"12","key":"299_CR1","doi-asserted-by":"publisher","first-page":"1661","DOI":"10.1016\/j.dam.2012.03.025","volume":"160","author":"O Amini","year":"2012","unstructured":"Amini, O., Peleg, D., P\u00e9rennes, S., Sau, I., Saurabh, S.: On the approximability of some degree-constrained subgraph problems. Discret. Appl. Math. 160(12), 1661\u20131679 (2012). doi:\n                        10.1016\/j.dam.2012.03.025","journal-title":"Discret. Appl. Math."},{"issue":"4","key":"299_CR2","doi-asserted-by":"publisher","first-page":"804","DOI":"10.1145\/4221.4227","volume":"32","author":"B Awerbuch","year":"1985","unstructured":"Awerbuch, B.: Complexity of network synchronization. J. ACM 32(4), 804\u2013823 (1985). doi:\n                        10.1145\/4221.4227","journal-title":"J. ACM"},{"key":"299_CR3","doi-asserted-by":"publisher","unstructured":"Azar, Y.: On-line load balancing. In: Fiat, A., Woeginger, G.J. (eds.) Online Algorithms. Lecture Notes in Computer Science, vol. 1442, pp. 178\u2013195. Springer, Berlin (1998). doi:\n                        10.1007\/BFb0029569","DOI":"10.1007\/BFb0029569"},{"issue":"2","key":"299_CR4","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1006\/jagm.1995.1008","volume":"18","author":"Y Azar","year":"1995","unstructured":"Azar, Y., Naor, J., Rom, R.: The competitiveness of on-line assignments. J. Algorithms 18(2), 221\u2013237 (1995). doi:\n                        10.1006\/jagm.1995.1008","journal-title":"J. Algorithms"},{"key":"299_CR5","doi-asserted-by":"publisher","unstructured":"Barenboim, L., Elkin, M., Pettie, S., Schneider, J.: The locality of distributed symmetry breaking. J. ACM 63(3), 20:1\u201320:45 (2016). doi:\n                        10.1145\/2903137","DOI":"10.1145\/2903137"},{"issue":"4\u20135","key":"299_CR6","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1016\/j.dam.2011.11.007","volume":"160","author":"D Bokal","year":"2012","unstructured":"Bokal, D., Bre\u0161ar, B., Jerebic, J.: A generalization of hungarian method and Hall\u2019s theorem with applications in wireless sensor networks. Discret. Appl. Math. 160(4\u20135), 460\u2013470 (2012). doi:\n                        10.1016\/j.dam.2011.11.007","journal-title":"Discret. Appl. Math."},{"key":"299_CR7","doi-asserted-by":"publisher","unstructured":"Czygrinow, A., Han\u0107kowiak, M., Szyma\u0144ska, E., Wawrzyniak, W.: Distributed 2-approximation algorithm for the semi-matching problem. In: 26th DISC, pp. 210\u2013222 (2012). doi:\n                        10.1007\/978-3-642-33651-5_15","DOI":"10.1007\/978-3-642-33651-5_15"},{"issue":"2","key":"299_CR8","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/S0020-0190(97)00196-8","volume":"65","author":"A Dessmark","year":"1998","unstructured":"Dessmark, A., Garrido, O., Lingas, A.: A note on parallel complexity of maximum f-matching. Inform. Process. Lett. 65(2), 107\u2013109 (1998). doi:\n                        10.1016\/S0020-0190(97)00196-8","journal-title":"Inform. Process. Lett."},{"key":"299_CR9","doi-asserted-by":"publisher","unstructured":"D\u00f3sa, G., Epstein, L.: The convergence time for selfish bin packing. In: 7th SAGT, pp. 37\u201348 (2014). doi:\n                        10.1007\/978-3-662-44803-8_4","DOI":"10.1007\/978-3-662-44803-8_4"},{"key":"299_CR10","doi-asserted-by":"publisher","unstructured":"Even-Dar, E., Kesselman, A., Mansour, Y.: Convergence time to Nash equilibrium in load balancing. ACM T. Algorithms 3(3), 32 (2007). doi:\n                        10.1145\/1273340.1273348","DOI":"10.1145\/1273340.1273348"},{"issue":"3","key":"299_CR11","doi-asserted-by":"publisher","first-page":"14:1","DOI":"10.1145\/2601071","volume":"10","author":"J Fakcharoenphol","year":"2014","unstructured":"Fakcharoenphol, J., Laekhanukit, B., Nanongkai, D.: Faster algorithms for semi-matching problems. ACM Trans. Algorithms 10(3), 14:1\u201314:3 (2014). doi:\n                        10.1145\/2601071","journal-title":"ACM Trans. Algorithms"},{"issue":"1","key":"299_CR12","doi-asserted-by":"publisher","first-page":"117","DOI":"10.1142\/S0129626406002514","volume":"16","author":"M Gairing","year":"2006","unstructured":"Gairing, M., L\u00fccking, T., Mavronicolas, M., Monien, B.: The price of anarchy for restricted parallel links. Parallel Process. Lett. 16(1), 117\u2013131 (2006). doi:\n                        10.1142\/S0129626406002514","journal-title":"Parallel Process. Lett."},{"key":"299_CR13","doi-asserted-by":"publisher","unstructured":"Gal\u010d\u00edk, F., Katreni\u010d, J., Semani\u0161in, G.: On computing an optimal semi-matching. In: 37th WG, pp. 250\u2013261 (2011). doi:\n                        10.1007\/978-3-642-25870-1_23","DOI":"10.1007\/978-3-642-25870-1_23"},{"issue":"1","key":"299_CR14","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/s00453-009-9386-0","volume":"58","author":"N Garg","year":"2010","unstructured":"Garg, N., Kavitha, T., Kumar, A., Mehlhorn, K., Mestre, J.: Assigning papers to referees. Algorithmica 58(1), 119\u2013136 (2010). doi:\n                        10.1007\/s00453-009-9386-0","journal-title":"Algorithmica"},{"key":"299_CR15","unstructured":"Halld\u00f3rsson, M.M., K\u00f6hler, S., Rawitz, D.: Distributed approximation of \n                        $$k$$\n                        \n                            \n                                k\n                            \n                        \n                    -service assignment. In: 19th International Conference on Principles of Distributed Systems, pp. 122\u2013137 (2015)"},{"key":"299_CR16","doi-asserted-by":"publisher","unstructured":"Ha\u0144\u0107kowiak, M., Karo\u0144ski, M., Panconesi, A.: A faster distributed algorithm for computing maximal matchings deterministically. In: 18th PODC, pp. 219\u2013228 (1999). doi:\n                        10.1145\/301308.301360","DOI":"10.1145\/301308.301360"},{"issue":"1","key":"299_CR17","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1016\/j.jalgor.2005.01.003","volume":"59","author":"NJA Harvey","year":"2006","unstructured":"Harvey, N.J.A., Ladner, R.E., Lov\u00e1sz, L., Tamir, T.: Semi-matchings for bipartite graphs and load balancing. J. Algorithms 59(1), 53\u201378 (2006). doi:\n                        10.1016\/j.jalgor.2005.01.003","journal-title":"J. Algorithms"},{"issue":"1","key":"299_CR18","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1007\/s00037-006-0205-6","volume":"15","author":"E Hazan","year":"2006","unstructured":"Hazan, E., Safra, S., Schwartz, O.: On the complexity of approximating \n                        $$k$$\n                        \n                            \n                                k\n                            \n                        \n                    -set packing. Comput. Complex. 15(1), 20\u201339 (2006). doi:\n                        10.1007\/s00037-006-0205-6","journal-title":"Comput. Complex."},{"issue":"4","key":"299_CR19","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1137\/0202019","volume":"2","author":"JE Hopcroft","year":"1973","unstructured":"Hopcroft, J.E., Karp, R.M.: An \n                        $$n^{5\/2}$$\n                        \n                            \n                                \n                                    n\n                                    \n                                        5\n                                        \/\n                                        2\n                                    \n                                \n                            \n                        \n                     algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2(4), 225\u2013231 (1973). doi:\n                        10.1137\/0202019","journal-title":"SIAM J. Comput."},{"issue":"1","key":"299_CR20","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1016\/0020-0190(91)90246-E","volume":"37","author":"V Kann","year":"1991","unstructured":"Kann, V.: Maximum bounded 3-dimensional matching is MAX SNP-complete. Inform. Process. Lett. 37(1), 27\u201335 (1991). doi:\n                        10.1016\/0020-0190(91)90246-E","journal-title":"Inform. Process. Lett."},{"issue":"3","key":"299_CR21","doi-asserted-by":"publisher","first-page":"559","DOI":"10.7151\/dmgt.1694","volume":"33","author":"J Katreni\u010d","year":"2013","unstructured":"Katreni\u010d, J., Semani\u0161in, G.: Maximum semi-matching problem in bipartite graphs. Discuss. Math. Graph Theory 33(3), 559\u2013569 (2013). doi:\n                        10.7151\/dmgt.1694","journal-title":"Discuss. Math. Graph Theory"},{"key":"299_CR22","doi-asserted-by":"publisher","unstructured":"K\u00f6hler, S., Turau, V., Mentges, G.: Self-stabilizing local \n                        $$k$$\n                        \n                            \n                                k\n                            \n                        \n                    -placement of replicas with minimal variance. In: 14th SSS, pp. 16\u201330 (2012). doi:\n                        10.1007\/978-3-642-33536-5_2","DOI":"10.1007\/978-3-642-33536-5_2"},{"issue":"1","key":"299_CR23","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1007\/s00446-011-0127-7","volume":"24","author":"C Koufogiannakis","year":"2011","unstructured":"Koufogiannakis, C., Young, N.E.: Distributed algorithms for covering, packing and maximum weighted matching. Distrib. Comput. 24(1), 45\u201363 (2011). doi:\n                        10.1007\/s00446-011-0127-7","journal-title":"Distrib. Comput."},{"issue":"5","key":"299_CR24","doi-asserted-by":"publisher","first-page":"38:1","DOI":"10.1145\/2786753","volume":"62","author":"Z Lotker","year":"2015","unstructured":"Lotker, Z., Patt-Shamir, B., Pettie, S.: Improved distributed approximate matching. J. ACM 62(5), 38:1\u201338:17 (2015). doi:\n                        10.1145\/2786753","journal-title":"J. ACM"},{"issue":"4","key":"299_CR25","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/j.ipl.2006.06.004","volume":"100","author":"CP Low","year":"2006","unstructured":"Low, C.P.: An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs. Inform. Process. Lett. 100(4), 154\u2013161 (2006). doi:\n                        10.1016\/j.ipl.2006.06.004","journal-title":"Inform. Process. Lett."},{"issue":"2","key":"299_CR26","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/PL00008932","volume":"14","author":"A Panconesi","year":"2001","unstructured":"Panconesi, A., Rizzi, R.: Some simple distributed algorithms for sparse networks. Distrib. Comput. 14(2), 97\u2013100 (2001). doi:\n                        10.1007\/PL00008932","journal-title":"Distrib. Comput."},{"issue":"3","key":"299_CR27","doi-asserted-by":"publisher","first-page":"402","DOI":"10.1016\/j.jpdc.2011.12.003","volume":"72","author":"B Patt-Shamir","year":"2012","unstructured":"Patt-Shamir, B., Rawitz, D., Scalosub, G.: Distributed approximation of cellular coverage. J. Parallel Distrib. Comput. 72(3), 402\u2013408 (2012). doi:\n                        10.1016\/j.jpdc.2011.12.003","journal-title":"J. Parallel Distrib. Comput."},{"key":"299_CR28","doi-asserted-by":"crossref","unstructured":"Peleg, D.: Distributed Computing: A Locality-Sensitive Approach. Society for Industrial and Applied Mathematics, Philadelphia (2000)","DOI":"10.1137\/1.9780898719772"},{"issue":"2","key":"299_CR29","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/0020-0190(81)90009-0","volume":"12","author":"Y Shiloach","year":"1981","unstructured":"Shiloach, Y.: Another look at the degree constrained subgraph problem. Inform. Process. Lett. 12(2), 89\u201392 (1981). doi:\n                        10.1016\/0020-0190(81)90009-0","journal-title":"Inform. Process. Lett."},{"key":"299_CR30","doi-asserted-by":"crossref","unstructured":"V\u00f6cking, B.: Selfish load balancing. In: Nisan, N., Roughgarden, T., Tardos, E., Vazirani, V. (eds.) Algorithmic Game Theory, pp. 699\u2013716. Cambridge University Press, Cambridge (2007)","DOI":"10.1017\/CBO9780511800481.022"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-017-0299-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-017-0299-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-017-0299-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2018,3,11]],"date-time":"2018-03-11T22:53:46Z","timestamp":1520808826000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-017-0299-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,6,3]]},"references-count":30,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2018,4]]}},"alternative-id":["299"],"URL":"https:\/\/doi.org\/10.1007\/s00446-017-0299-x","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2017,6,3]]}}}