article

A general approach to online network optimization problems

Authors:

Baruch Awerbuch,

Niv Buchbinder,

Joseph (Seffi) NaorAuthors Info & Claims

ACM Transactions on Algorithms (TALG), Volume 2, Issue 4

Pages 640 - 660

https://doi.org/10.1145/1198513.1198522

Published: 01 October 2006 Publication History

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 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 O(log m)-competitive deterministic algorithm for generating a 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 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äcke's new hierarchical decomposition of graphs.Specifically, our results for the integral case include an O(log mlog 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, 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²nlog k)-competitive randomized algorithm for the online group Steiner problem in trees and an O(log³nlog 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³nlog log n)-competitive algorithm for the online multi-cut problem.

References

[1]

Alon, N., Awerbuch, B., Azar, Y., Buchbinder, N., and Naor, J. 2003. The online set cover problem. In Proceedings of the 35th Annual ACM Symposium on the Theory of Computation. ACM, New York, 100--105.

Digital Library

[2]

Alon, N., and Spencer, J. H. 2000. The Probabilistic Method, 2nd Ed. Wiley, New York.

[3]

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.

Digital Library

[4]

Bartal, Y. 1996. Probabilistic approximation of metric spaces and its algorithmic applications. In Proceedings of the 37th Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 184--193.

Digital Library

[5]

Berman, P., and Coulston, C. 1997. On-line algorithms for Steiner tree problems. In Proceedings of the 29th Annual ACM Symposium on the Theory of Computation. 344--353.

Digital Library

[6]

Bienkowski, M., Korzeniowski, M., and Räcke, H. 2003. A practical algorithm for constructing oblivious routing schemes. In Proceedings of the 15th ACM Symposium on Parallelism in Algorithms and Architectures. ACM, New York, 24--33.

Digital Library

[7]

Fotakis, D. 2003. On the competitive ratio for online facility location. In Proceedings of the 30th International Colloquium on Automata, Languages and Programming. 637--652.

Digital Library

[8]

Fakcharoenphol, J., Rao, S., and Talwar, K. 2003. A tight bound on approximating arbitrary metrics by tree metrics. In Proceedings of the 35th annual ACM Symposium on Theory of Computation. ACM, New York, 448--455.

Digital Library

[9]

Garg, N., Konjevod, G., and Ravi, R. 2003. A polylogarithmic approximation algorithm for the group Steiner tree problem. J. Algorithms 37, 66--84.

Digital Library

[10]

Garg, N., Vazirani, V. V., and Yannakakis, M. 1996. Approximate max-flow min-(multi)cut theorems and their applications. SIAM J. Comput. 25, 235--251.

Digital Library

[11]

Garg, N., Vazirani, V. V., and Yannakakis, M. 1997. Primal-dual approximation algorithms for integral flow and multicut in trees. Algorithmica 18, 3--20.

Digital Library

[12]

Harrelson, C., Hidrum, K., and Rao, S. 2003. A polynomial time tree decomposition to minimize congestion. In Proceedings of the 15th ACM Symposium on Parallelism in Algorithms and Architectures. ACM, New York, 34--43.

Digital Library

[13]

Hochbaum, D. S. 1997. Approximation Algorithms. PWS Publishing Company.

Digital Library

[14]

Imase, M. and Waxman, B. M. 1991. Dynamic Steiner tree problem. SIAM J. Disc. Math 4, 369--384.

[15]

Meyerson, A. 2001. Online facility location. In Proceedings of the 42nd Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 426--431.

Digital Library

[16]

Plotkin, S. A., Shmoys, D., and Tardos, E. 1995. Fast approximation algorithms for fractional packing and covering problems. Math. Oper. Res. 20, 257--301.

Digital Library

[17]

Räcke, H. 2002. Minimizing congestion in general networks. In Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society Press, Los Alamitos, CA, 43--52.

Digital Library

[18]

Vazirani, V. V. 2001. Approximation Algorithms. Springer-Verlag, New York.

Digital Library

Cited By

Nagarajan VWang L(2024)Online Generalized Network Design Under (Dis)Economies of ScaleMathematics of Operations Research10.1287/moor.2022.134949:1(107-124)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1287/moor.2022.1349
Bhore STóth C(2024)Online Euclidean SpannersACM Transactions on Algorithms10.1145/368179021:1(1-22)Online publication date: 4-Nov-2024
https://dl.acm.org/doi/10.1145/3681790
Bhore SFiltser AKhodabandeh HTóth C(2024)Online Spanners in Metric SpacesSIAM Journal on Discrete Mathematics10.1137/22M153457238:1(1030-1056)Online publication date: 12-Mar-2024
https://doi.org/10.1137/22M1534572
Show More Cited By

Index Terms

A general approach to online network optimization problems
1. Theory of computation

Recommendations

The online set cover problem
STOC '03: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing

Let X=[1,2,•••,n] be a ground set of n elements, and let S be a family of subsets of X, |S|=m, with a positive cost c_S associated with each S ∈ S.Consider the following online version of the set cover problem, described as a game between an algorithm ...
A general approach to online network optimization problems
SODA '04: Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms

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 ...
Online algorithms with advice for bin packing and scheduling problems

We consider the setting of online computation with advice and study the bin packing problem and a number of scheduling problems. We show that it is possible, for any of these problems, to arbitrarily approach a competitive ratio of 1 with only a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Algorithms

ACM Transactions on Algorithms Volume 2, Issue 4

October 2006

233 pages

ISSN:1549-6325

EISSN:1549-6333

DOI:10.1145/1198513

Issue’s Table of Contents

Copyright © 2006 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 2006

Published in TALG Volume 2, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

72
Total Citations
View Citations
1,205
Total Downloads

Downloads (Last 12 months)83
Downloads (Last 6 weeks)18

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Nagarajan VWang L(2024)Online Generalized Network Design Under (Dis)Economies of ScaleMathematics of Operations Research10.1287/moor.2022.134949:1(107-124)Online publication date: 1-Feb-2024
https://dl.acm.org/doi/10.1287/moor.2022.1349
Bhore STóth C(2024)Online Euclidean SpannersACM Transactions on Algorithms10.1145/368179021:1(1-22)Online publication date: 4-Nov-2024
https://dl.acm.org/doi/10.1145/3681790
Bhore SFiltser AKhodabandeh HTóth C(2024)Online Spanners in Metric SpacesSIAM Journal on Discrete Mathematics10.1137/22M153457238:1(1030-1056)Online publication date: 12-Mar-2024
https://doi.org/10.1137/22M1534572
Markarian C(2024)Online Algorithmic Study of Facility Location Problems: A SurveyIEEE Access10.1109/ACCESS.2024.340678812(77724-77738)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3406788
Bhattacharya SBuchbinder NLevin RSaranurak T(2023)Chasing Positive Bodies2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS57990.2023.00103(1694-1714)Online publication date: 6-Nov-2023
https://doi.org/10.1109/FOCS57990.2023.00103
Huang ZLi MShu XWei T(2023)Online Nash Welfare Maximization Without PredictionsWeb and Internet Economics10.1007/978-3-031-48974-7_23(402-419)Online publication date: 4-Dec-2023
https://dl.acm.org/doi/10.1007/978-3-031-48974-7_23
Markarian CKhallouf P(2023)Online Facility Location Problems Inspired by the COVID-19 PandemicInnovative Intelligent Industrial Production and Logistics10.1007/978-3-031-37228-5_7(110-123)Online publication date: 7-Jul-2023
https://doi.org/10.1007/978-3-031-37228-5_7
Joswig MSchröter B(2022)Parametric Shortest-Path Algorithms via Tropical GeometryMathematics of Operations Research10.1287/moor.2021.119947:3(2065-2081)Online publication date: 1-Aug-2022
https://dl.acm.org/doi/10.1287/moor.2021.1199
Sadrhaghighi SDolati MGhaderi MKhonsari A(2022)FlowShark: Sampling for High Flow Visibility in SDNsIEEE INFOCOM 2022 - IEEE Conference on Computer Communications10.1109/INFOCOM48880.2022.9796658(160-169)Online publication date: 2-May-2022
https://doi.org/10.1109/INFOCOM48880.2022.9796658
Gupta AKehne GLevin R(2022)Random Order Online Set Cover is as Easy as Offline2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS)10.1109/FOCS52979.2021.00122(1253-1264)Online publication date: Feb-2022
https://doi.org/10.1109/FOCS52979.2021.00122
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents