CONSTRUCTING RELIABLE COMMUNICATION-NETWORKS OF SMALL WEIGHT ONLINE

Suppose the vertices of a complete weighted graph are revealed to us o ne at a time, and we have to build a network with some desired propert ies on these vertices. We consider the cost of building a network whic h has these properties after the addition of each vertex and compare i t 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 hav e been revealed. We examine online algorithms for constructing network s with three properties; high connectivity, low vertex degree, and sma ll diameter, and evaluate these algorithms from the competitive perspe ctive. 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 compe titive ratio of any online algorithm. We also present an online algori thm with a competitive ratio of O(k(2) log n) to build a k-connected n etwork with maximum vertex degree 3k and an online algorithm with a co mpetitive 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 Academic Press, Inc,