Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(10)
Community Networks
Competitive Ratio
Facility Location
Graphs and Networks
Network Design
Network Optimization
Online Algorithm
Optimization Problem
Randomized Algorithm
Satisfiability
Related Publications
(8)
The allornothing multicommodity flow problem
The online set cover problem
Solving Symmetri...
Finding effective supporttree preconditioners
An optimal algorithm for online bipartite matching
Subscribe
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
Edit
A general approach to online network optimization problems
(
Citations: 42
)
BibTex

RIS

RefWorks
Download
Noga Alon
,
Baruch Awerbuch
,
Yossi Azar
,
Niv Buchbinder
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 nonmetric
facility location
and for a generalization of the problem called themulticast problem. In the nonmetric
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 online 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 multicut 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:
ACMSIAM Symposium on Discrete Algorithms  SODA
, pp. 577586, 2004
DOI:
10.1145/982792.982879
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.
(
portal.acm.org
)
(
portal.acm.org
)
(
www.cs.tau.ac.il
)
(
www.informatik.unitrier.de
)
(
www.cs.jhu.edu
)
(
www.math.tau.ac.il
)
(
doi.acm.org
)
(
portal.acm.org
)
More »
Citation Context
(28)
...Alon et al. [
2
] introduced the generalized connectivity problem to study online network formation settings, and showed that it captures several wellstudied problems, such as Steiner forest, nonmetric facility location, tree multicast, and group Steiner tree...
...On the positive side, Alon et al. [
2
] devised a multiplicativeupdate online algorithm for computing logcompetitive fractional solutions to generalized connectivity...
...Finally, it is possible to obtain a polylogarithmic 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 Chekuri
,
et 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 siti path, for some si 2 S i and ti 2 Ti. Alon et al. demonstrated that this broader class of demands ...
Danny Segev
,
et 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 primaldual based algorithms for fractional generalized network design...
Anupam Gupta
,
et 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 earoptimalO(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 (edgeweighted) connectivity and ...
Spyros Angelopoulos
.
Online Priority Steiner Tree Problems
References
(20)
Dynamic Steiner Tree Problem
(
Citations: 181
)
Makoto Imase
,
Bernard M. Waxman
Journal:
Siam Journal on Discrete Mathematics  SIAMDM
, vol. 4, no. 3, pp. 369384, 1991
A polynomialtime tree decomposition to minimize congestion
(
Citations: 72
)
Chris Harrelson
,
Kirsten Hildrum
,
Satish Rao
Conference:
ACM Symposium on Parallel Algorithms and Architectures  SPAA
, pp. 3443, 2003
A tight bound on approximating arbitrary metrics by tree metrics
(
Citations: 310
)
Jittat Fakcharoenphol
,
Satish Rao
,
Kunal Talwar
Conference:
ACM Symposium on Theory of Computing  STOC
, pp. 448455, 2003
Online generalized Steiner problem
(
Citations: 51
)
Baruch Awerbuch
,
Yossi Azart
,
Yair Bartal
Conference:
ACMSIAM Symposium on Discrete Algorithms  SODA
, pp. 6874, 1996
A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem
(
Citations: 122
)
Naveen Garg
,
Goran Konjevod
,
R. Ravi
Journal:
Journal of Algorithms  JAL
, vol. 37, no. 1, pp. 6684, 2000
Sort by:
Citations
(42)
A Unified Approach to Approximating Partial Covering Problems
(
Citations: 1
)
Jochen Könemann
,
Ojas Parekh
,
Danny Segev
Journal:
Algorithmica
, vol. 59, no. 4, pp. 489509, 2011
Set connectivity problems in undirected graphs and the directed steiner network problem
Chandra Chekuri
,
Guy Even
,
Anupam Gupta
,
Danny Segev
Journal:
ACM Transactions on Algorithms  TALG
, vol. 7, no. 2, pp. 117, 2011
Online and incremental algorithms for facility location
Dimitris Fotakis
Journal:
Sigact News  SIGACT
, vol. 42, no. 1, pp. 97131, 2011
Approximating
Danny Segev
Journal:
Journal of Combinatorial Optimization  JCO
, vol. 21, no. 3, pp. 364382, 2011
Inferring Social Networks from Outbreaks
(
Citations: 1
)
Dana Angluin
,
James Aspnes
,
Lev Reyzin
Conference:
Algorithmic Learning Theory  ALT
, pp. 104118, 2010