{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:25:14Z","timestamp":1759638314996},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2010,12,7]],"date-time":"2010-12-07T00:00:00Z","timestamp":1291680000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2011,11]]},"DOI":"10.1007\/s00224-010-9303-6","type":"journal-article","created":{"date-parts":[[2010,12,6]],"date-time":"2010-12-06T05:03:32Z","timestamp":1291611812000},"page":"672-697","source":"Crossref","is-referenced-by-count":9,"title":["Local Approximability of Max-Min and Min-Max Linear Programs"],"prefix":"10.1007","volume":"49","author":[{"given":"Patrik","family":"Flor\u00e9en","sequence":"first","affiliation":[]},{"given":"Marja","family":"Hassinen","sequence":"additional","affiliation":[]},{"given":"Joel","family":"Kaasinen","sequence":"additional","affiliation":[]},{"given":"Petteri","family":"Kaski","sequence":"additional","affiliation":[]},{"given":"Topi","family":"Musto","sequence":"additional","affiliation":[]},{"given":"Jukka","family":"Suomela","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2010,12,7]]},"reference":[{"key":"9303_CR1","first-page":"82","volume-title":"Proc. 12th Annual ACM Symposium on Theory of Computing (STOC)","author":"D. Angluin","year":"1980","unstructured":"Angluin, D.: Local and global properties in networks of processors. In: Proc. 12th Annual ACM Symposium on Theory of Computing (STOC), Los Angeles, CA, USA, April 1980, pp. 82\u201393. ACM, New York (1980)"},{"key":"9303_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"191","DOI":"10.1007\/978-3-642-04355-0_21","volume-title":"Proc. 23rd International Symposium on Distributed Computing (DISC)","author":"M. \u00c5strand","year":"2009","unstructured":"\u00c5strand, M., Flor\u00e9en, P., Polishchuk, V., Rybicki, J., Suomela, J., Uitto, J.: A local 2-approximation algorithm for the vertex cover problem. In: Proc. 23rd International Symposium on Distributed Computing (DISC), Elche, Spain, September 2009. Lecture Notes in Computer Science, vol. 5805, pp.\u00a0191\u2013205. Springer, Berlin (2009)"},{"key":"9303_CR3","doi-asserted-by":"crossref","first-page":"294","DOI":"10.1145\/1810479.1810533","volume-title":"Proc. 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)","author":"M. \u00c5strand","year":"2010","unstructured":"\u00c5strand, M., Suomela, J.: Fast distributed approximation algorithms for vertex cover and set cover in anonymous networks. In: Proc. 22nd Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Santorini, Greece, June 2010, pp. 294\u2013302. ACM, New York (2010)"},{"key":"9303_CR4","first-page":"206","volume-title":"Proc. 29th Annual Symposium on Foundations of Computer Science (FOCS)","author":"B. Awerbuch","year":"1988","unstructured":"Awerbuch, B., Sipser, M.: Dynamic networks are as fast as static networks. In: Proc. 29th Annual Symposium on Foundations of Computer Science (FOCS), White Plains, NY, USA, October 1988, pp.\u00a0206\u2013219. IEEE, Piscataway (1988)."},{"key":"9303_CR5","doi-asserted-by":"crossref","first-page":"258","DOI":"10.1109\/SFCS.1991.185377","volume-title":"Proc. 32nd Annual Symposium on Foundations of Computer Science (FOCS)","author":"B. Awerbuch","year":"1991","unstructured":"Awerbuch, B., Varghese, G.: Distributed program checking: a paradigm for building self-stabilizing distributed protocols. In: Proc. 32nd Annual Symposium on Foundations of Computer Science (FOCS), San Juan, Puerto Rico, October 1988, pp. 258\u2013267. IEEE, Piscataway (1991)."},{"issue":"1","key":"9303_CR6","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B.S. Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41(1), 153\u2013180 (1994)","journal-title":"J. ACM"},{"key":"9303_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"78","DOI":"10.1007\/978-3-540-87779-0_6","volume-title":"Proc. 22nd International Symposium on Distributed Computing (DISC)","author":"A. Czygrinow","year":"2008","unstructured":"Czygrinow, A., Ha\u0144\u0107kowiak, M., Wawrzyniak, W.: Fast distributed approximations in planar graphs. In: Proc. 22nd International Symposium on Distributed Computing (DISC), Arcachon, France, September 2008. Lecture Notes in Computer Science, vol. 5218, pp. 78\u201392. Springer, Berlin (2008)"},{"key":"9303_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"2","DOI":"10.1007\/978-3-540-92862-1_2","volume-title":"Proc. 4th International Workshop on Algorithmic Aspects of Wireless Sensor Networks (Algosensors)","author":"P. Flor\u00e9en","year":"2008","unstructured":"Flor\u00e9en, P., Hassinen, M., Kaski, P., Suomela, J.: Tight local approximation results for max-min linear programs. In: Proc. 4th International Workshop on Algorithmic Aspects of Wireless Sensor Networks (Algosensors), Reykjav\u00edk, Iceland, July 2008. Lecture Notes in Computer Science, vol. 5389, pp.\u00a02\u201317. Springer, Berlin (2008)"},{"key":"9303_CR9","first-page":"260","volume-title":"Proc. 21st Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)","author":"P. Flor\u00e9en","year":"2009","unstructured":"Flor\u00e9en, P., Kaasinen, J., Kaski, P., Suomela, J.: An optimal local approximation algorithm for max-min linear programs. In: Proc. 21st Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Calgary, Canada, August 2009, pp. 260\u2013269. ACM, New York (2009)"},{"key":"9303_CR10","volume-title":"Proc. 22nd IEEE International Parallel and Distributed Processing Symposium (IPDPS)","author":"P. Flor\u00e9en","year":"2008","unstructured":"Flor\u00e9en, P., Kaski, P., Musto, T., Suomela, J.: Approximating max-min linear programs with local algorithms. In: Proc. 22nd IEEE International Parallel and Distributed Processing Symposium (IPDPS), Miami, FL, USA, April 2008. IEEE, Piscataway (2008)"},{"issue":"1","key":"9303_CR11","doi-asserted-by":"crossref","first-page":"102","DOI":"10.1007\/s00453-009-9353-9","volume":"58","author":"P. Flor\u00e9en","year":"2010","unstructured":"Flor\u00e9en, P., Kaski, P., Polishchuk, V., Suomela, J.: Almost stable matchings by truncating the Gale\u2013Shapley algorithm. Algorithmica 58(1), 102\u2013118 (2010)","journal-title":"Algorithmica"},{"key":"9303_CR12","first-page":"219","volume-title":"Proc. 9th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"M. Ha\u0144\u0107kowiak","year":"1998","unstructured":"Ha\u0144\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, January 1998, pp. 219\u2013225. Society for Industrial and Applied Mathematics, Philadelphia (1998)"},{"issue":"1","key":"9303_CR13","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1145\/2455.214106","volume":"32","author":"D.S. Hochbaum","year":"1985","unstructured":"Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM 32(1), 130\u2013136 (1985)","journal-title":"J. ACM"},{"key":"9303_CR14","unstructured":"Hoory, S.: On graphs of high girth. PhD thesis, Hebrew University, Jerusalem (March 2002)"},{"key":"9303_CR15","unstructured":"Kuhn, F.: The price of locality: exploring the complexity of distributed coordination primitives. PhD thesis, ETH Z\u00fcrich (2005)"},{"key":"9303_CR16","volume-title":"Proc. 26th IEEE International Conference on Distributed Computing Systems (ICDCS)","author":"F. Kuhn","year":"2006","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: Fault-tolerant clustering in ad hoc and sensor networks. In: Proc. 26th IEEE International Conference on Distributed Computing Systems (ICDCS), Lisboa, Portugal, July 2006. IEEE Computer Society Press, Los Alamitos (2006)"},{"key":"9303_CR17","doi-asserted-by":"crossref","first-page":"980","DOI":"10.1145\/1109557.1109666","volume-title":"Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"F. Kuhn","year":"2006","unstructured":"Kuhn, F., Moscibroda, T., Wattenhofer, R.: The price of being near-sighted. In: Proc. 17th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), Miami, FL, USA, January 2006, pp. 980\u2013989. ACM, New York (2006)"},{"key":"9303_CR18","first-page":"46","volume-title":"Proc. 20th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA)","author":"C. Lenzen","year":"2008","unstructured":"Lenzen, C., Oswald, Y.A., Wattenhofer, R.: What can be approximated locally? In: Proc. 20th Annual ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), Munich, Germany, June 2008, pp. 46\u201354. ACM, New York (2008)"},{"key":"9303_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/978-3-642-05118-0_2","volume-title":"Proc. 11th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS)","author":"C. Lenzen","year":"2009","unstructured":"Lenzen, C., Suomela, J., Wattenhofer, R.: Local algorithms: self-stabilization on speed. In: Proc. 11th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), Lyon, France, November 2009. Lecture Notes in Computer Science, vol. 5873, pp. 17\u201334. Springer, Berlin (2009)"},{"key":"9303_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"394","DOI":"10.1007\/978-3-540-87779-0_27","volume-title":"Proc. 22nd International Symposium on Distributed Computing (DISC)","author":"C. Lenzen","year":"2008","unstructured":"Lenzen, C., Wattenhofer, R.: Leveraging Linial\u2019s locality limit. In: Proc. 22nd International Symposium on Distributed Computing (DISC), Arcachon, France, September 2008. Lecture Notes in Computer Science, vol. 5218, pp. 394\u2013407. Springer, Berlin (2008)"},{"issue":"1","key":"9303_CR21","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1137\/0221015","volume":"21","author":"N. Linial","year":"1992","unstructured":"Linial, N.: Locality in distributed graph algorithms. SIAM J. Comput. 21(1), 193\u2013201 (1992)","journal-title":"SIAM J. Comput."},{"key":"9303_CR22","doi-asserted-by":"crossref","first-page":"268","DOI":"10.1109\/ISTCS.1995.377023","volume-title":"Proc. 3rd Israel Symposium on the Theory of Computing and Systems (ISTCS)","author":"A. Mayer","year":"1995","unstructured":"Mayer, A., Naor, M., Stockmeyer, L.: Local computations on static and dynamic graphs. In: Proc. 3rd Israel Symposium on the Theory of Computing and Systems (ISTCS), Tel Aviv, Israel, January 1995, pp. 268\u2013278. IEEE, Piscataway (1995)."},{"key":"9303_CR23","unstructured":"Moscibroda, T.: Locality, scheduling, and selfishness: algorithmic foundations of highly decentralized networks. PhD thesis, ETH Z\u00fcrich (2006)"},{"issue":"6","key":"9303_CR24","doi-asserted-by":"crossref","first-page":"1259","DOI":"10.1137\/S0097539793254571","volume":"24","author":"M. Naor","year":"1995","unstructured":"Naor, M., Stockmeyer, L.: What can be computed locally? SIAM J. Comput. 24(6), 1259\u20131277 (1995)","journal-title":"SIAM J. Comput."},{"key":"9303_CR25","first-page":"121","volume-title":"Proc. 25th Annual ACM Symposium on Theory of Computing (STOC)","author":"C.H. Papadimitriou","year":"1993","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Linear programming without the matrix. In: Proc. 25th Annual ACM Symposium on Theory of Computing (STOC), San Diego, CA, USA, May 1993, pp. 121\u2013129. ACM, New York (1993)"},{"issue":"12","key":"9303_CR26","doi-asserted-by":"crossref","first-page":"642","DOI":"10.1016\/j.ipl.2009.02.017","volume":"109","author":"V. Polishchuk","year":"2009","unstructured":"Polishchuk, V., Suomela, J.: A simple local 3-approximation algorithm for vertex cover. Inf. Process. Lett. 109(12), 642\u2013645 (2009)","journal-title":"Inf. Process. Lett."},{"key":"9303_CR27","unstructured":"Suomela, J.: Optimisation problems in wireless sensor networks: local algorithms and local graphs. PhD thesis, University of Helsinki, Department of Computer Science, Helsinki, Finland (May 2009)"},{"key":"9303_CR28","unstructured":"Suomela, J.: Survey of local algorithms. http:\/\/www.iki.fi\/jukka.suomela\/local-survey (2009). Manuscript submitted for publication"},{"key":"9303_CR29","doi-asserted-by":"crossref","first-page":"538","DOI":"10.1109\/SFCS.2001.959930","volume-title":"Proc. 42nd Annual Symposium on Foundations of Computer Science (FOCS)","author":"N.E. Young","year":"2001","unstructured":"Young, N.E.: Sequential and parallel algorithms for mixed packing and covering. In: Proc. 42nd Annual Symposium on Foundations of Computer Science (FOCS), Las Vegas, NV, USA, October 2001, pp. 538\u2013546. IEEE Computer Society Press, Los Alamitos (2001)"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-010-9303-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-010-9303-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-010-9303-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,6]],"date-time":"2019-06-06T20:50:30Z","timestamp":1559854230000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-010-9303-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12,7]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,11]]}},"alternative-id":["9303"],"URL":"https:\/\/doi.org\/10.1007\/s00224-010-9303-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,12,7]]}}}