Many optimization problems that arise in various industries, including logistics, production planning, transportation and telecommunication, have to be solved repeatedly and in automated fashion. In many cases, the underlying mathematical optimization problem is provably hard, and cannot be solved to optimality in a reasonable amount of time. As a result, the task of the algorithm designer is to develop algorithms that are efficient and provide good solutions on every single run, as a far from optimum solution even just once might be catastrophic, either in terms of the cost of the solution obtained or in terms of its inability to meet demands or other constraints. This stresses the importance of designing efficient algorithms for hard combinatorial optimization problems that deliver solutions guaranteed to be probably close to the optimum. This area of approximation algorithms has seen a tremendous growth in the last decade, with a host of new results.
The intellectual merit of this proposal is to develop new methodologies and techniques to provide the algorithm designer with the tools to design approximation algorithms and is also to focus on crucial problems. These problems include fundamental problems such as the traveling salesman problem and other network problems which arise as building blocks in many industrial settings. A special emphasis will be given to settings in which the data evolves over time and the algorithm's task is to provide a constantly changing solution to meet the fluctuating requirements. This solution needs to be robust against these fluctuations, and remain close to optimum at any time.
The broader impact of this proposal is to provide industry with the tools to be more productive and more efficiently use the available resources, and this in turn will have an impact on the economy. The proposal also seeks funds for the training of graduate students and this is important to maintain the competitively of our workforce and guarantee the best possible training for the next generation of faculty members teaching on our college campuses.
