Online Network Design
Adam Meyerson, Stanford University


Abstract:
Many optimization problems can be applied to the design of networks. In particular, facility location has received a great deal of attention in recent years. Another example of a network design problem is buy-at-bulk, in which we must purchase cables in order to connect a set of demands to a core network. These problems have applications in the design of intranets, telecommunication networks, and reservation of bandwidth on existing networks, as well as a number of transportation and shipment problems from operations research.

We observe that the applications for network design are naturally online. He set of demands changes with time, often necessitating changes to an existing network (rebuilding the network from scratch when the demands change is not economically feasible). With this in mind, we present online competitive algorithms for facility location and the problem of access network design. These algorithms produce solutions within a provable competitive ratio of the best which could be done offline with unlimited computation time and full knowledge of the demand set.

We will also introduce a notion of incremental algorithms; by removing part of the adversarial assumption from online analysis we can obtain better competitive ratios.