Selfish routing in the presence of side constraints

The natural approach for describing network flow problems is to introduce side constraints that capture restrictions of a logical or technological nature, e.g., capacity constraints. We study the traffic equilibria arising from selfish routing of individual users in networks with side constraints. We examine first the case of linear latency functions. Under very general assumptions … Read more

Faster Approximation Schemes for Fractional Multicommodity Flow Problems

We present fully polynomial approximation schemes for concurrent multicommodity flow problems that run in time of minimal dependency on the number of commodities k. We show that by modifying the algorithms by Garg & Konemann and Fleischer we can reduce their running time to a logarithmic dependence on k, and essentially match the running time … Read more