We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.
We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.
Published online by Cambridge University Press: 07 May 2024
Introduction
In this chapter, we consider a canonical network flow problem, popularly known as multicommodity routing, where the network is represented as a directed graph. Each flow request identifies a source–destination pair and a flow demand, i.e., the amount of flow going from the source to the destination (possibly over multiple paths of the graph) should be at least as much as the demand. Each edge of the graph is equipped with a latency function, and the cost of an edge is equal to the latency function evaluated at the total flow passing through it. Requests arrive sequentially or in an online manner, and have to be routed irrevocably using only the causal information, and the goal is to minimize the sum of the cost of all edges after all request arrivals.
Unlike many other problems considered in this book, the offline optimal solution is easy to find by solving a convex program. On the online front, however, an optimal online algorithm is not known. We consider both the splittable and the unsplittable cases (where only one path can be used to route the demand for each source–destination pair). For both cases, we consider affine latency functions and present the best-known guarantees on the competitive ratio that are achieved by a locally optimal algorithm that solves a convex program on each request arrival given the past routing decisions.
It is worthwhile noting that the unsplittable problem considered in this chapter is similar to the network load balancing problem studied in Section 12.4, where the objective was to minimize the maximum load exerted on any one edge of the network. Compared to that objective, in this chapter, we consider minimizing the sum of the ‘loads’ exerted on all edges of the network via summing the latency functions of each edge evaluated at their flow allocation. This new cost function has a fundamentally different competitive ratio guarantee compared to the network load balancing problem. In particular, we showed in Chapter 12 that the best competitive ratio for the network load balancing problem scales as Θ(log(n)), where n is the number of vertices in the network graph. In contrast, we will show that for affine latency functions, a simple algorithm is constant competitive.
To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.
Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.
Find out more about the Kindle Personal Document Service.
To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.
To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.
