The Design of Competitive Online Algorithms via a Primal-Dual Approach V: Online RoutingTextbook
Network routing is one of the paradigmatic applications of the online primal-dual method:
requests for bandwidth between a source and target arrive one at a time, and the algorithm must
commit bandwidth to paths without knowing future requests. Chapter 4 already gave a simple
(3, O(log n))-competitive routing algorithm as an illustration of the general…