{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,12]],"date-time":"2026-06-12T10:14:20Z","timestamp":1781259260080,"version":"3.54.1"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Algorithms"],"published-print":{"date-parts":[[2006,10]]},"abstract":"\n We study a wide range of online graph and network optimization problems, focusing on problems that arise in the study of connectivity and cuts in graphs. In a general online network design problem, we have a communication network known to the algorithm in advance. What is not known in advance are the connectivity (bandwidth) or cut demands between vertices in the network which arrive online.We develop a unified framework for designing online algorithms for problems involving connectivity and cuts. We first present a general\n O<\/jats:italic>\n (log\n m<\/jats:italic>\n )-competitive deterministic algorithm for generating a fractional solution that satisfies the online connectivity or cut demands, where\n m<\/jats:italic>\n is the number of edges in the graph. This may be of independent interest for solving fractional online bandwidth allocation problems, and is applicable to both directed and undirected graphs. We then show how to obtain integral solutions via an online rounding of the fractional solution. This part of the framework is problem dependent, and applies various tools including results on approximate max-flow min-cut for multicommodity flow, the Hierarchically Separated Trees (HST) method and its extensions, certain rounding techniques for dependent variables, and R\u00e4cke's new hierarchical decomposition of graphs.Specifically, our results for the integral case include an\n O<\/jats:italic>\n (log\n m<\/jats:italic>\n log\n n<\/jats:italic>\n )-competitive randomized algorithm for the online nonmetric facility location problem and for a generalization of the problem called the multicast problem. In the nonmetric facility location problem,\n m<\/jats:italic>\n is the number of facilities and\n n<\/jats:italic>\n is the number of clients. The competitive ratio is nearly tight. We also present an\n O<\/jats:italic>\n (log\n 2<\/jats:sup>\n n<\/jats:italic>\n log\n k<\/jats:italic>\n )-competitive randomized algorithm for the online group Steiner problem in trees and an\n O<\/jats:italic>\n (log\n 3<\/jats:sup>\n n<\/jats:italic>\n log\n k<\/jats:italic>\n )-competitive randomized algorithm for the problem in general graphs, where\n n<\/jats:italic>\n is the number of vertices in the graph and\n k<\/jats:italic>\n is the number of groups. Finally, we design a deterministic\n O<\/jats:italic>\n (log\n 3<\/jats:sup>\n n<\/jats:italic>\n log log\n n<\/jats:italic>\n )-competitive algorithm for the online multi-cut problem.\n <\/jats:p>","DOI":"10.1145\/1198513.1198522","type":"journal-article","created":{"date-parts":[[2007,4,5]],"date-time":"2007-04-05T19:20:08Z","timestamp":1175800808000},"page":"640-660","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":65,"title":["A general approach to online network optimization problems"],"prefix":"10.1145","volume":"2","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[{"name":"Tel-Aviv University, Tel-Aviv, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Baruch","family":"Awerbuch","sequence":"additional","affiliation":[{"name":"Johns Hopkins University, Baltimore, MD"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yossi","family":"Azar","sequence":"additional","affiliation":[{"name":"Tel-Aviv University, Tel-Aviv, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Niv","family":"Buchbinder","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Joseph (Seffi)","family":"Naor","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2006,10]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780558"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Alon N. and Spencer J. H. 2000. The Probabilistic Method 2nd Ed. Wiley New York. Alon N. and Spencer J. H. 2000. The Probabilistic Method 2nd Ed. Wiley New York.","DOI":"10.1002\/0471722154"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Awerbuch B.","unstructured":"Awerbuch , B. , Azar , Y. , and Bartal , Y . 2001. On-line generalized Steiner problem . In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM , New York, 68--74. Awerbuch, B., Azar, Y., and Bartal, Y. 2001. On-line generalized Steiner problem. In Proceedings of the 7th Annual ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 68--74."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875536"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258618"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/777412.777418"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/1759210.1759273"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780608"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1096"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793243016"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523685"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/777412.777419"},{"key":"e_1_2_1_13_1","volume-title":"Approximation Algorithms","author":"Hochbaum D. S.","unstructured":"Hochbaum , D. S. 1997. Approximation Algorithms . PWS Publishing Company . Hochbaum, D. S. 1997. Approximation Algorithms. PWS Publishing Company."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404033"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/874063.875567"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.20.2.257"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/645413.652152"},{"key":"e_1_2_1_18_1","volume-title":"Approximation Algorithms","author":"Vazirani V. V.","unstructured":"Vazirani , V. V. 2001. Approximation Algorithms . Springer-Verlag , New York . Vazirani, V. V. 2001. Approximation Algorithms. Springer-Verlag, New York."}],"container-title":["ACM Transactions on Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1198513.1198522","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T20:33:34Z","timestamp":1672259614000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1198513.1198522"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006,10]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2006,10]]}},"alternative-id":["10.1145\/1198513.1198522"],"URL":"https:\/\/doi.org\/10.1145\/1198513.1198522","relation":{},"ISSN":["1549-6325","1549-6333"],"issn-type":[{"value":"1549-6325","type":"print"},{"value":"1549-6333","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006,10]]},"assertion":[{"value":"2006-10-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}