As the world becomes increasingly connected and embedded in computational systems, network algorithms have the potential for tremendous impact. A key challenge is that, despite the enormous progress in computing, connectivity and data analytics, uncertainty remains pervasive in all aspects of life and we need a fundamental shift in the definition of what solutions we seek. For example, what is the optimal route under uncertain traffic? That depends on the risk-averseness of a user, who would seek to balance minimizing expected delay and the variability of the route. How can we compute this risk-minimizing route? More generally, how can we compute risk-minimizing solutions in complex networks and how is risk defined? Risk has been at the forefront of research and practice in finance and economics. However, there is still a major need for designing computational approaches corresponding to these risk models, as well as developing new risk models and solution techniques that are specific to networked systems.
The goal of this CAREER project is to lay the algorithmic foundation of a new area of risk mitigation for networked systems (such as transportation, telecommunications, energy, etc.) via an interdisciplinary approach that unifies Computer Science, Operations Research, Economics and Finance. The technical milestones are to: (1) Develop a comprehensive theory of risk models for networked systems, in part inspired by risk models in finance and economics, and in part driven by the specific requirements of networked systems; (2) Advance the classic theory of algorithms, in which all input data is available upfront, by integrating uncertainty and risk---this will be achieved by developing novel techniques for nonlinear and nonconvex combinatorial optimization; (3) Leverage dynamic data to improve adaptive decision-making, using and advancing tools from Markov Decision Processes and developing new tools for approximating the optimal solutions; (4) Further the theory of online algorithms for repeated decision-making by developing reductions from nonlinear (risk-averse) formulations to the standard linear formulations.
On a high level, the transformative potential of the proposed research is to fundamentally shift thinking about stochastic problems in the field of network algorithms away from expected performance and instead towards understanding and mitigating risk. The research is motivated by problems of national importance in transportation, telecommunications and energy. It has the potential to improve a variety of applications that involve uncertainty and risk-averse users, for example, reducing congestion in transportation and telecommunication networks, improving the operation of the smart grid, etc. The PI will actively work on building bridges to other disciplines, for example, via organizing interdisciplinary workshops. The PI will also participate in high-school outreach programs, summer camps for undergraduates and programs for increasing the participation of women and underrepresented minorities in computing.
