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(log2n log k) competitive randomized algorithm for the on-line group Steiner problem in trees and an O(log3n 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(log3n 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.
No takes yet. Share an insight, caveat, or question.
Alon et al. (2004) studied this question.
Synapse has enriched 2 closely related papers on similar clinical questions. Consider them for comparative context: