A General Approach to Online Network Optimization Problems

Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph Naor

Research output: Contribution to conferencePaper

24 Scopus citations

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 the multicast 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 an O (log 2 n log k) competitive randomized algorithm for the online group Steiner problem in trees and an O(log 3n 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 3 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. This may be of independent interest for solving fractional online bandwidth allocation problems, and is applicable to the node version as well. The integral solutions are obtained by an online rounding of the fractional solution. This part of the framework is problem dependent, and applies various tools including results on the approximate max-flow min-cut for multicommodity flow, the HST method and its extensions, certain rounding techniques for dependent variables, and Räcke's new hierarchical decomposition of graphs.

Original languageEnglish (US)
Pages570-579
Number of pages10
StatePublished - Apr 15 2004
Externally publishedYes
EventProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms - New Orleans, LA., United States
Duration: Jan 11 2004Jan 13 2004

Other

OtherProceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms
CountryUnited States
CityNew Orleans, LA.
Period1/11/041/13/04

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'A General Approach to Online Network Optimization Problems'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., & Naor, J. (2004). A General Approach to Online Network Optimization Problems. 570-579. Paper presented at Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, New Orleans, LA., United States.