{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:39:22Z","timestamp":1787337562950,"version":"build-2736575974"},"reference-count":19,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2004,1]]},"abstract":"<jats:p>We study combinatorial optimization problems in which a set of distributed agents must achieve a global objective using only local information. Papadimitriou and Yannakakis [Proceedings of the 25th ACM Symposium on Theory of Computing, 1993, pp. 121--129] initiated the study of such problems in a framework where distributed decision-makers must generate feasible solutions to positive linear programs with information only about local constraints. We extend their model by allowing these distributed decision-makers to perform local communication to acquire information over time and then explore the tradeoff between the amount of communication and the quality of the solution to the linear program that the decision-makers can obtain.<\/jats:p>\n                  <jats:p>Our main result is a distributed algorithm that obtains a $(1 + \\epsilon)$ approximation to the optimal linear programming solution while using only a polylogarithmic number of rounds of local communication. This algorithm offers a significant improvement over the logarithmic approximation ratio previously obtained by Awerbuch and Azar [Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, 1994, pp. 240--249] for this problem while providing a comparable running time. Our results apply directly to the application of network flow control, an application in which distributed routers must quickly choose how to allocate bandwidth to connections using only local information to achieve global objectives. The sequential version of our algorithm is faster and considerably simpler than the best known approximation algorithms capable of achieving a $(1 + \\epsilon)$ approximation ratio for positive linear programming.<\/jats:p>","DOI":"10.1137\/s0097539700379383","type":"journal-article","created":{"date-parts":[[2004,8,13]],"date-time":"2004-08-13T21:00:26Z","timestamp":1092430826000},"page":"1261-1279","source":"Crossref","is-referenced-by-count":13,"title":["Fast, Distributed Approximation Algorithms for Positive Linear Programming with Applications to Flow Control"],"prefix":"10.1137","volume":"33","author":[{"given":"Yair","family":"Bartal","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John W.","family":"Byers","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Danny","family":"Raz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2012,2,17]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Yehuda Afek, Yishay Mansour, Zvi Ostfeld, Convergence complexity of optimistic rate based flow control algorithms (extended abstract), ACM, New York, 1996, 89\u2013981427502","DOI":"10.1145\/237814.237837"},{"key":"R2","unstructured":"J. Aspnes, Y. Azar, A. Fiat, S. Plotkin, and O. Waarts,\n                      On\u2010line load balancing with applications to machine scheduling and virtual circuit routing\n                      , in Proceedings of the 33rd Annual IEEE Symposium on Foundations of Computer Science, 1992, pp. 164\u2013173."},{"key":"R3","unstructured":"B. Awerbuch and Y. Azar,\n                      Local optimization of global objectives: Competitive distributed deadlock resolution and resource allocation\n                      , in Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, 1994, pp. 240\u2013249."},{"key":"R4","doi-asserted-by":"crossref","unstructured":"B. Awerbuch, Y. Azar, and S. Plotkin,\n                      Throughput competitive on\u2010line routing\n                      , in Proceedings of the 34th Annual IEEE Symposium on Foundations of Computer Science, 1993, pp. 32\u201340.","DOI":"10.1109\/SFCS.1993.366884"},{"key":"R5","doi-asserted-by":"crossref","unstructured":"B. Awerbuch and Y. Shavitt,\n                      Converging to approximated max\u2010min flow fairness in logarithmic time\n                      , in Proceedings of the 17th IEEE INFOCOM Conference, 1998, pp. 1350\u20131357.","DOI":"10.1109\/INFCOM.1998.662951"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"Y. Bartal, J. Byers, and D. Raz,\n                      Achieving global objectives using local information with applications to flow control\n                      , in Proceedings of the 38th Annual IEEE Symposium on Foundations of Computer Science, Miami Beach, FL, 1997, pp. 303\u2013312.","DOI":"10.1109\/SFCS.1997.646119"},{"key":"R7","unstructured":"D. Bertsekas and R. Gallagher,\n                      Data Networks\n                      , Prentice\u2010Hall, Englewood Cliffs, NJ, 1987."},{"key":"R8","volume-title":"Potential function methods for approximately solving linear programming problems: theory and practice","author":"Bienstock Daniel","year":"2002"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1109\/65.372653"},{"key":"R10","unstructured":"J. Byers,\n                      Maximizing Throughput of Reliable Bulk Network Transmissions\n                      , Ph.D. Thesis, University of California at Berkeley, Berkeley, CA, 1997."},{"key":"R11","unstructured":"A. Charny,\n                      An Algorithm for Rate Allocation in a Packet\u2010Switching Network with Feedback\n                      , Technical Report MIT\/LCS\/TR\u2010601, MIT Laboratory for Computer Science, Cambridge, MA, 1994."},{"key":"R12","doi-asserted-by":"crossref","unstructured":"N. Garg and J. Koenemann,\n                      Faster and simpler algorithms for multicommodity flow and other fractional packing problems\n                      , in Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998, pp. 300\u2013309.","DOI":"10.1109\/SFCS.1998.743463"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1109\/TCOM.1981.1095081"},{"key":"R14","unstructured":"H. Karloff,\n                      Linear Programming\n                      , Birkh\u00e4user, Boston, MA, 1996."},{"key":"R15","doi-asserted-by":"crossref","unstructured":"N. Linial,\n                      Distributive graph algorithms\u2014global solutions from local data\n                      , in Proceedings of the 28th Annual IEEE Symposium on Foundations of Computer Science, 1987, pp. 331\u2013335.","DOI":"10.1109\/SFCS.1987.20"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1109\/90.811451"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"M. Luby and N. Nisan,\n                      A parallel approximation algorithm for positive linear programming\n                      , in Proceedings of the 25th ACM Symposium on Theory of Computing, 1993, pp. 448\u2013457.","DOI":"10.1145\/167088.167211"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"C. Papadimitriou and M. Yannakakis,\n                      Linear programming without the matrix\n                      , in Proceedings of the 25th ACM Symposium on Theory of Computing, 1993, pp. 121\u2013129.","DOI":"10.1145\/167088.167127"},{"key":"R19","doi-asserted-by":"crossref","unstructured":"Serge Plotkin, David Shmoys, \u00c9va Tardos, Fast approximation algorithms for fractional packing and covering problems, IEEE Comput. Soc. Press, Los Alamitos, CA, 1991, 495\u201350493j:90083","DOI":"10.1109\/SFCS.1991.185411"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539700379383","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:17:41Z","timestamp":1787336261000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539700379383"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2004,1]]},"references-count":19,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2004,1]]}},"alternative-id":["10.1137\/S0097539700379383"],"URL":"https:\/\/doi.org\/10.1137\/s0097539700379383","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2004,1]]}}}