Allocation of Resources under Dependencies

We consider the problem of how to decide which projects to invest in and implement in a transportation network, so as to maximize the total utility of the road network after project implementation. Two important issues that make this an interesting mathematical problem are: first, local changes in a transportation network can lead to agglomerative changes in its global behavior; second, multiple projects within a certain geographical area of the transportation network may be proposed for implementation simultaneously, which means that such projects cannot be considered independent of each other.

I will discuss the work done with colleagues in Civil Engineering and Computer Science department on this problem in the recent past. I will report on the new holistic model we developed and how it compares computationally with previous models on real data from I-DOT (Illinois Department of Transportation). Our results clearly show that our models capture the effects of dependency between different projects. Ignoring these effects gives a false inflated benefit from a collection of projects leading to erroneous decision-making.

This research also led to work approximation algorithms for the related Graph and Hypergraph Knapsack problems, generalizations of the classical Knapsack problem that take dependencies between items into account. I will discuss the connections between this work and classical problems in combinatorial optimization and extremal graph theory.