In many diverse applications such as road traffic and data networks, users strategically choose routes in a network to minimize the delay they face. Routing games model this strategic behavior of the users, and are used to understand and predict the impact of this behavior on the traffic and delays in the network. 

We consider a fundamental problem facing the manager of such a network: to make improvements to the network under a fixed budget, so that the average delay for the strategic users is minimized. The problem is modeled using routing games and widely studied in transportation research. However, despite its practical relevance, there are no proven guarantees for polynomial-time algorithms. In this talk, I will present both algorithms and hardness results for this problem.