  


Selfish routing in the presence of side constraints
George Karakostas (karakosmcmaster.ca) Abstract: 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 for the side constraints we show that the total latency of the routes chosen by selfish network users is at most 4/3 times the minimum possible total latency. This matches the known lower bound. For general latency functions we formulate the traffic equilibrium as the solution to a nonlinear complementarity problem. We use a classic transformation to reduce the existence of a solution to the complementarity problem to the existence of a fixed point for an appropriate continuous function. Such a fixed point always exists if a set of Lagrangean multipliers from the complementarity problem is bounded from above. As an application we cast the recent optimal taxes result of Cole, Dodis and Roughgarden in this general framework. Keywords: traffic equilibria, side constraints Category 1: Network Optimization Citation: Tech. report CAS0313GK, Dept. of Computing & Software, McMaster University, Hamilton, Ontario Canada Submitted 11/2003 Download: [PDF] Entry Submitted: 12/22/2003 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  