A general approach to online network optimization problems

ABSTRACT

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 bandwidth or cut demands between nodes in the network. Our results include an O(log m log n) competitive randomized algorithm for the online non-metric facility location and for a generalization of the problem called themulticast problem. In the non-metric facility location m is the number of facilities and n is the number of clients. The competitive ratio is nearly tight. We also present anO(log² n log k) competitive randomized algorithm for the on-line group Steiner problem in trees and an O(log³ n log k)competitive randomized algorithm for the problem in general graphs, where n is the number of vertices in the graph and k is the number of groups. Finally, we design a deterministic O(log³ n log log n) competitive algorithm for the online multi-cut problem. Our algorithms are based on a unified framework for designing online algorithms for problems involving connectivity and cuts. We first present a general O(log m)-deterministic algorithm for generating fractional solution that satisfies the online connectivity or cut demands, where m is the number of edges in the graph.

REFERENCES

• 1: Noga Alon , Baruch Awerbuch , Yossi Azar, The online set cover problem, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780558]
• 2: N. Alon and J. H. Spencer, The probabilistic method, Second Edition, Wiley, New York, 2000.
• 3: Baruch Awerbuch , Yossi Azar , Yair Bartal, On-line generalized Steiner problem, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.68-74, January 28-30, 1996, Atlanta, Georgia, United States
• 4: Y. Bartal, Probabilistic approximation of metric spaces and its algorithmic applications, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.184, October 14-16, 1996
• 5: Piotr Berman , Chris Coulston, On-line algorithms for Steiner tree problems (extended abstract), Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.344-353, May 04-06, 1997, El Paso, Texas, United States [doi>10.1145/258533.258618]
• 6: Marcin Bienkowski , Miroslaw Korzeniowski , Harald Räcke, A practical algorithm for constructing oblivious routing schemes, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777418]
• 7: Dimitris Fotakis. On the competitive ratio for online facility location. In ICALP 2003, pp. 637--652 2003.
• 8: Jittat Fakcharoenphol , Satish Rao , Kunal Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Proceedings of the thirty-fifth annual ACM symposium on Theory of computing, June 09-11, 2003, San Diego, CA, USA [doi>10.1145/780542.780608]
• 9: Naveen Garg , Goran Konjevod , R. Ravi, A polylogarithmic approximation algorithm for the group Steiner tree problem, Journal of Algorithms, v.37 n.1, p.66-84, Oct. 2000 [doi>10.1006/jagm.2000.1096]
• 10: Naveen Garg , Vijay V. Vazirani , Mihalis Yannakakis, Approximate Max-Flow Min-(Multi)Cut Theorems and Their Applications, SIAM Journal on Computing, v.25 n.2, p.235-251, February 1996 [doi>10.1137/S0097539793243016]
• 11: N. Garg, V. V. Vazirani and M. Yannakakis. Primal-dual approximation algorithms for integral flow and multicut in trees. In Algorithmica, 18:3--20, 1997.
• 12: Chris Harrelson , Kirsten Hildrum , Satish Rao, A polynomial-time tree decomposition to minimize congestion, Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures, June 07-09, 2003, San Diego, California, USA [doi>10.1145/777412.777419]
• 13: Dorit S. Hochbaum, Approximation algorithms for NP-hard problems, PWS Publishing Co., Boston, MA, 1996
• 14: M. Imase and B. M. Waxman. Dynamic Steiner tree problem. In SIAM Journal Discrete Math., 4:369--384, 1991.
• 15: A. Meyerson, Online Facility Location, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.426, October 14-17, 2001
• 16: Harald Räcke, Minimizing Congestion in General Networks, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.43-52, November 16-19, 2002
• 17: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001