{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:10:06Z","timestamp":1760202606515,"version":"3.37.3"},"reference-count":40,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2010,3,30]],"date-time":"2010-03-30T00:00:00Z","timestamp":1269907200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Distrib. Comput."],"published-print":{"date-parts":[[2010,5]]},"DOI":"10.1007\/s00446-010-0100-x","type":"journal-article","created":{"date-parts":[[2010,3,29]],"date-time":"2010-03-29T15:10:29Z","timestamp":1269875429000},"page":"269-283","source":"Crossref","is-referenced-by-count":15,"title":["Fast primal-dual distributed algorithms for scheduling and matching problems"],"prefix":"10.1007","volume":"22","author":[{"given":"Alessandro","family":"Panconesi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mauro","family":"Sozio","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2010,3,30]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"Albers, S., Arora, S., Khanna, S.: Page replacement for general caching problems. In: SODA, pp. 31\u201340 (1999)","key":"100_CR1","DOI":"10.1111\/an.1999.40.5.31.4"},{"issue":"1","key":"100_CR2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0166-218X(87)90037-0","volume":"18","author":"E.M. Arkin","year":"1987","unstructured":"Arkin E.M., Silverberg E.B.: Scheduling jobs with fixed start and end times. Discrete Appl. Math. 18(1), 1\u20138 (1987)","journal-title":"Discrete Appl. Math."},{"issue":"5","key":"100_CR3","doi-asserted-by":"crossref","first-page":"1069","DOI":"10.1145\/502102.502107","volume":"48","author":"A. Bar-Noy","year":"2001","unstructured":"Bar-Noy A., Bar-Yehuda R., Freund A., Naor J., Schiebe B.: A unified approach to approximating resource allocation and scheduling. J. ACM 48(5), 1069\u20131090 (2001)","journal-title":"J. ACM"},{"issue":"2","key":"100_CR4","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1137\/S0097539799354138","volume":"31","author":"A. Bar-Noy","year":"2001","unstructured":"Bar-Noy A., Guha S., Naor J., Schieber B.: Approximating the throughput of multiple machines in real-time scheduling. SIAM J. Comput 31(2), 331\u2013352 (2001)","journal-title":"SIAM J. Comput"},{"unstructured":"Chudak, F., Erlebach, T., Panconesi, A., Sozio, M.: Primal-dual distributed algorithms for covering and facility location problems. In: Manuscript (2006)","key":"100_CR5"},{"doi-asserted-by":"crossref","unstructured":"Dessmark, A., Lingas, A., Garrido, O.: On parallel complexity of maximum f-matching and the degree sequence problem. In: MFCS, pp. 316\u2013325 (1994)","key":"100_CR6","DOI":"10.1007\/3-540-58338-6_78"},{"issue":"2","key":"100_CR7","doi-asserted-by":"crossref","first-page":"179","DOI":"10.1142\/S0129054193000122","volume":"4","author":"K. Diks","year":"1993","unstructured":"Diks K., Garrido O., Lingas A.: Parallel algorithms for finding maximal k-dependent sets and maximal f-matchings. Int. J. Found. Comput. Sci 4(2), 179\u2013192 (1993)","journal-title":"Int. J. Found. Comput. Sci"},{"doi-asserted-by":"crossref","unstructured":"Dimitrov, N.B., Roy, I.: A primal-dual resource augmentation analysis of a constant approximate algorithm for stable coalitions in a cluster. In: SPAA, pp. 236\u2013245 (2008)","key":"100_CR8","DOI":"10.1145\/1378533.1378578"},{"unstructured":"Dubhashi, D., Grandoni, F., Panconesi, A.: Distributed approximation algorithms via LP-duality and randomization. In: Gonzalez, T. (ed.) Handbook on Approximation Algorithms and Metaheuristics. Chapman & Hall\/CRC, Computer and Information Science Series","key":"100_CR9"},{"key":"100_CR10","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511581274","volume-title":"Concentration of measure for the analysis of randomized algorithms","author":"D. Dubhashi","year":"2009","unstructured":"Dubhashi D., Panconesi A.: Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, New York (2009)"},{"key":"100_CR11","doi-asserted-by":"crossref","first-page":"869","DOI":"10.1002\/nav.10092","volume":"50","author":"S. Dye","year":"2003","unstructured":"Dye S., Stougie L., Tomasgard A.: The stochastic single resource service-provision problem. Nav. Res. Logistics 50, 869\u2013887 (2003)","journal-title":"Nav. Res. Logistics"},{"issue":"3","key":"100_CR12","doi-asserted-by":"crossref","first-page":"115","DOI":"10.1016\/0020-0190(93)90055-E","volume":"46","author":"T. Fischer","year":"1993","unstructured":"Fischer T., Goldberg A.V, Haglin D.J., Plotkin S.A.: Approximating matchings in parallel. Inf. Process. Lett. 46(3), 115\u2013118 (1993)","journal-title":"Inf. Process. Lett."},{"doi-asserted-by":"crossref","unstructured":"Flor\u00e9en, P., Hassinen, M., Kaski, P., Suomela, J.: Tight local approximation results for max-\u00a0min linear programs. In: ALGOSENSORS, pp. 2\u201317 (2008)","key":"100_CR13","DOI":"10.1007\/978-3-540-92862-1_2"},{"doi-asserted-by":"crossref","unstructured":"Gergov, J.: Approximation algorithms for dynamic storage allocations. In: ESA, pp. 52\u201361 (1996)","key":"100_CR14","DOI":"10.1007\/3-540-61680-2_46"},{"key":"100_CR15","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0167-5060(08)70356-X","volume":"5","author":"R.L. Graham","year":"1979","unstructured":"Graham R.L., Lawler E.L., Lenstra J.K., Kan A.H.G.R.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5, 287\u2013326 (1979)","journal-title":"Ann. Discrete Math."},{"issue":"3","key":"100_CR16","doi-asserted-by":"crossref","first-page":"825","DOI":"10.1137\/06065310X","volume":"38","author":"F. Grandoni","year":"2008","unstructured":"Grandoni F., K\u00f6nemann J., Panconesi A., Sozio M.: A primal-dual bicriteria distributed algorithm for capacitated vertex cover. SIAM J. Comput. 38(3), 825\u2013840 (2008)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"100_CR17","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1137\/S0895480100373121","volume":"15","author":"M. Hanckowiak","year":"2001","unstructured":"Hanckowiak M., Karonski M., Panconesi A.: On the distributed complexity of computing maximal matchings. SIAM J. Discrete Math. 15(1), 41\u201357 (2001)","journal-title":"SIAM J. Discrete Math."},{"unstructured":"Hoepman, J.H.: Simple distributed weighted matchings. CoRR cs.DC\/0410047 (2004)","key":"100_CR18"},{"unstructured":"Khuller, S., Vishkin, U., Young, N.E.: A primal-dual parallel approximation technique applied to weighted set and vertex cover. CoRR cs.DS\/0205037 (2002)","key":"100_CR19"},{"doi-asserted-by":"crossref","unstructured":"Koufogiannakis, C., Young, N.E.: Distributed and parallel algorithms for weighted vertex cover and other covering problems. In: PODC, pp. 171\u2013179 (2009)","key":"100_CR20","DOI":"10.1145\/1582716.1582746"},{"doi-asserted-by":"crossref","unstructured":"Koufogiannakis, C., Young, N.E.: Distributed fractional packing and maximum weighted b-matching via tail-recursive duality. In: DISC, pp. 221\u2013238 (2009)","key":"100_CR21","DOI":"10.1007\/978-3-642-04355-0_23"},{"doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T.: Distributed approximation of capacitated dominating sets. In: SPAA, pp. 161\u2013170 (2007)","key":"100_CR22","DOI":"10.1145\/1248377.1248403"},{"doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: On the locality of bounded growth. In: PODC, pp. 60\u201368 (2005)","key":"100_CR23","DOI":"10.1145\/1073814.1073826"},{"doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: Fault-tolerant clustering in ad hoc and sensor networks. In: ICDCS, pp. 68 (2006)","key":"100_CR24","DOI":"10.1109\/ICDCS.2006.40"},{"doi-asserted-by":"crossref","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: The price of being near-sighted. In: SODA, pp. 980\u2013989 (2006)","key":"100_CR25","DOI":"10.1145\/1109557.1109666"},{"issue":"4","key":"100_CR26","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1007\/s00446-004-0112-5","volume":"17","author":"F. Kuhn","year":"2005","unstructured":"Kuhn F., Wattenhofer R.: Constant-time distributed dominating set approximation. Distri. Comput. 17(4), 303\u2013310 (2005)","journal-title":"Distri. Comput."},{"doi-asserted-by":"crossref","unstructured":"Lotker, Z., Patt-Shamir, B., Pettie, S.: Improved distributed approximate matching. In: SPAA, pp. 129\u2013136 (2008)","key":"100_CR27","DOI":"10.1145\/1378533.1378558"},{"issue":"2","key":"100_CR28","doi-asserted-by":"crossref","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. 39(2), 445\u2013460 (2009)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"100_CR29","doi-asserted-by":"crossref","first-page":"1036","DOI":"10.1137\/0215074","volume":"15","author":"M. Luby","year":"1986","unstructured":"Luby M.: A simple parallel algorithm for the maximal independent set problem. SIAM J. Comput. 15(4), 1036\u20131053 (1986)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Luby, M., Nisan, N.: A parallel approximation algorithm for positive linear programming. In: STOC, pp. 448\u2013457 (1993)","key":"100_CR30","DOI":"10.1145\/167088.167211"},{"doi-asserted-by":"crossref","unstructured":"Moscibroda, T., Mutlu, O.: Distributed order scheduling and its application to multi-core dram controllers. In: PODC, pp. 365\u2013374 (2008)","key":"100_CR31","DOI":"10.1145\/1400751.1400799"},{"doi-asserted-by":"crossref","unstructured":"Moscibroda, T., Wattenhofer, R.: Facility location: distributed approximation. In: PODC, pp. 108\u2013117 (2005)","key":"100_CR32","DOI":"10.1145\/1073814.1073834"},{"doi-asserted-by":"crossref","unstructured":"Panconesi, A., Sozio, M.: Fast distributed scheduling via primal-dual. In: SPAA, pp. 229\u2013235 (2008)","key":"100_CR33","DOI":"10.1145\/1378533.1378577"},{"issue":"2","key":"100_CR34","doi-asserted-by":"crossref","first-page":"356","DOI":"10.1006\/jagm.1996.0017","volume":"20","author":"A. Panconesi","year":"1996","unstructured":"Panconesi A., Srinivasan A.: On the complexity of distributed network decomposition. J. Algorithms 20(2), 356\u2013374 (1996)","journal-title":"J. Algorithms"},{"doi-asserted-by":"crossref","unstructured":"Pandit, S., Pemmaraju, S.: Return of the primal-dual: distributed metric facility location. In: PODC, pp. 180\u2013189 (2009)","key":"100_CR35","DOI":"10.1145\/1582716.1582747"},{"doi-asserted-by":"crossref","unstructured":"Patt-Shamir, B., Rawitz, D., Scalosub, G.: Distributed approximation of cellular coverage. In: OPODIS, pp. 331\u2013345 (2008)","key":"100_CR36","DOI":"10.1007\/978-3-540-92221-6_22"},{"unstructured":"Phillips, C.A., Uma, R.N., Wein, J.: Off-line admission control for general scheduling problems. In: SODA, pp. 879\u2013888 (2000)","key":"100_CR37"},{"doi-asserted-by":"crossref","unstructured":"Schneider, J., Wattenhofer, R.: A log-star distributed maximal independent set\u00a0algorithm for growth-bounded graphs. In: PODC, pp. 35\u201344 (2008)","key":"100_CR38","DOI":"10.1145\/1400751.1400758"},{"doi-asserted-by":"crossref","unstructured":"Shmoys, D.B., Sozio, M.: Approximation algorithms for 2-stage stochastic scheduling problems. In: IPCO, pp. 145\u2013157 (2007)","key":"100_CR39","DOI":"10.1007\/978-3-540-72792-7_12"},{"doi-asserted-by":"crossref","unstructured":"Wattenhofer, M., Wattenhofer, R.: Distributed weighted matching. In: DISC, pp. 335\u2013348 (2004)","key":"100_CR40","DOI":"10.1007\/978-3-540-30186-8_24"}],"container-title":["Distributed Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-010-0100-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00446-010-0100-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00446-010-0100-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,19]],"date-time":"2025-02-19T19:05:26Z","timestamp":1739991926000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00446-010-0100-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,3,30]]},"references-count":40,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2010,5]]}},"alternative-id":["100"],"URL":"https:\/\/doi.org\/10.1007\/s00446-010-0100-x","relation":{},"ISSN":["0178-2770","1432-0452"],"issn-type":[{"type":"print","value":"0178-2770"},{"type":"electronic","value":"1432-0452"}],"subject":[],"published":{"date-parts":[[2010,3,30]]}}}