Academic
Publications
A general approach to online network optimization problems

A general approach to online network optimization problems,10.1145/982792.982879,Noga Alon,Baruch Awerbuch,Yossi Azar,Niv Buchbinder

A general approach to online network optimization problems   (Citations: 42)
BibTex | RIS | RefWorks Download
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(log2 n log k) competitive randomized algorithm for the on-line group Steiner problem in trees and an O(log3 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(log3 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.
Conference: ACM-SIAM Symposium on Discrete Algorithms - SODA , pp. 577-586, 2004
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
    • ...Alon et al. [2] introduced the generalized connectivity problem to study online network formation settings, and showed that it captures several well-studied problems, such as Steiner forest, nonmetric facility location, tree multicast, and group Steiner tree...
    • ...On the positive side, Alon et al. [2] devised a multiplicative-update online algorithm for computing log-competitive fractional solutions to generalized connectivity...
    • ...Finally, it is possible to obtain a poly-logarithmic competitive ratio for generalized connectivity in the online setting? Alon et al. [2] show an O(logm) competitive ratio for computing a fractional solution to the relaxation LPGC of generalized connectivity...

    Chandra Chekuriet al. Set connectivity problems in undirected graphs and the directed steine...

    • ...Generalized demands. In the context of online computation, Alon, Awerbuch, Azar, Buchbinder and Naor [2] introduced the generalized connectivity paradigm, in which each demand is of the form (S i; Ti), where S i and Ti are disjoint sets of vertices; this demand is said to be connected by a given subgraph when the latter contains an si-ti path, for some si 2 S i and ti 2 Ti. Alon et al. demonstrated that this broader class of demands ...

    Danny Segevet al. Approximate k -Steiner Forests via the Lagrangian Relaxation Technique...

    • ...In this paper, we use results of Alon et al. [3] for the online (weighted) set cover problem; the ideas here have been extended by Alon et al. [4] and Buchbinder and Naor [9] to get online primal-dual based algorithms for fractional generalized network design...

    Anupam Guptaet al. Online and stochastic survivable network design

    • ...[1,11,18]). A polynomial time algorithm for this problem was independently given by Bienkowski et al. [6] and Harrelson et al. [13]...

    Harald Räcke. Survey on Oblivious Routing Strategies

    • ...Theorem 1 and Theorem 2). The bound extends to randomized algorithms (Theorem 3). For the latter class of algorithms, the techniques introduced by Alon et al. [15] yield an ear-optimalO(log k log m)-competitive randomized algorithm, where m is the number of edges in the graph (c.f Theorem 4). Thus, when k is comparable to m, there exist efficient online algorithms regardless of the number of priority levels...
    • ...However, observe that the adversarial graph G requires at least an exponential number of vertices (and edges) in the number of requested terminals k. Thus the following question arises: if the number of edges is comparable to the number of terminals, can we achieve better competitive ratios? To answer this, we can use the framework of Alon et al. [15], which addresses online algorithms for broad classes of (edge-weighted) connectivity and ...

    Spyros Angelopoulos. Online Priority Steiner Tree Problems

Sort by: