Improved bounds for online routing and packing via a primal-dual approach

In this work we study a wide range of online and offline routing and packing problems with various objectives. We provide a unified approach, based on a clean primal-dual method, for the design of online algorithms for these problems, as well as improved bounds on the competitive factor. In particular, our analysis uses weak duality rather than a tailor made (i.e., problem specific) potential function. We demonstrate our ideas and results in the context of routing problems. Using our primal-dual approach, we develop a new generic online routing algorithm that outperforms previous algorithms suggested earlier by Y. Azar et al. (1993, 1997). We then show the applicability of our generic algorithm to various models and provide improved algorithms for achieving coordinate-wise competitiveness, maximizing throughput, and minimizing maximum load. In particular, we improve the results obtained by A. Goel et al. (2001) by an O(log n) factor for the problem of achieving coordinate-wise competitiveness, and by an O(log log n) factor for the problem of maximizing the throughput. For some of the settings we also prove improved lower bounds. We believe our results further our understanding of the applicability of the primal-dual method to online algorithms, and we are confident that the method will prove useful to other online scenarios. Finally, we revisit the notions of coordinate-wise and prefix competitiveness in an offline setting. We design the first polynomial time algorithm that computes an almost optimal coordinate-wise routing for several routing models. We also revisit previously studied routing models by A. Kumar and J.M. Kleinberg (2000) and A. Goel and A. Meyerson (2005) and prove tight lower and upper bounds of Theta(log n) on prefix competitiveness for these models