CONSTRUCTING RELIABLE COMMUNICATION-NETWORKS OF SMALL WEIGHT ONLINE

Suppose the vertices of a complete weighted graph are revealed to us one at a time, and we have to build a network with some desired properties on these vertices. We consider the cost of building a network which has these properties after the addition of each vertex and compare it to the cost incurred by an algorithm which builds a network that has the same properties only at the end, i.e., after all the vertices have been revealed. We examine online algorithms for constructing networks with three properties; high connectivity, low vertex degree, and small diameter, and evaluate these algorithms from the competitive perspective. We show that on n points drawn from any metric space, a greedy algorithm constructs a k-connected network with a competitive ratio of O(k(2) log n), and prove a lower bound of Omega(k log n) on the competitive ratio of any online algorithm. We also present an online algorithm with a competitive ratio of O(k(2) log n) to build a k-connected network with maximum vertex degree 3k and an online algorithm with a competitive ratio of O(k(2) log n) to build a k-connected network with a diameter no more than a constant times the diameter of the n points. (C) 1995