Constructing Reliable Communication Networks of Small Weight Online
Abstract 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 Ω( 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 3 k 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.