Network design problems consist of selecting components to purchase (servers, cables, hubs, and so forth) in order to produce the cheapest network which satisfies given constraints. These constraints require (for example) high bandwidth or low latency service for a set of customers. Many such problems exist; some of the simplest can be solved using flow techniques. However, the addition of integrality constraints and economies of scale makes many network design problems NP-Hard.
I will describe combinatorial approximations for several problems in network design. In particular, I will presentthe problems of single sink buy-at-bulk network design and cost-distance network design. These problems deal with connecting a set of customers to a single sink node (consider this to be a point on the internet backbone). The customers have given bandwidth requirements and various types of cables are available whose costs satisfy economies of scale. The combinatorial approximation algorithms to be presented have a number of advantages over earlier techniques, improving running time, worst case approximation ratio, and average case performance.
Earlier work on network design did not account for changes in the set of customers with the passage of time. I will give the first online algorithm for facility location, making it possible to build a solution incrementally as the customers arrive. Similar techniques can be applied to the problem of access network design.
Finally, I will outline some avenues for future work, extending upon the results mentioned and relating them to current research in the theory and networking communities.
Parts of the work described are joint with Sudipto Guha, Kamesh Munagala, and Serge Plotkin.