CAREER: New Directions in Graph Algorithms

Duke University, Durham NC

Investigators

Abstract

Networks such as the Internet, social networks, transportation maps, and communication backbones have an ubiquitous presence in modern life. Graph algorithms play a crucial role in these networks by providing a range of basic services such as navigation, traffic management, and robustness against physical failures. Moreover, graphs are useful in modeling interactions in a variety of systems that arise in physical, biological, and social sciences. This project identifies a set of common themes in the algorithmic challenges that arise in modern networks -- uncertainty of data, complex failure patterns, and gigantic scale -- and seeks generic solutions that address these core issues. The project is expected to provide new insights into classical graph optimization problems, while also creating new models, problem formulations, and research directions that embrace these broad challenges. This project will also train graduate and undergraduate researchers in theoretical computer science, with an emphasis on gender diversity and participation of underrepresented groups. For over fifty years, graph algorithms have played a central role in the advancement of computer science, both in theory and practice. Modern networks have evolved in scale, structure, and functionality, inspiring new models, problems, and algorithms. This project focuses on three key research thrusts for modern graph algorithms: (a) network design under unreliable or imprecise future predictions, by developing generic optimization techniques for uncertain and dynamic inputs; (b) the analysis of correlation effects in network failures by expanding the scope of classical metrics like minimum cuts to incorporate correlated failures of multiple network components; and (c) the design of highly efficient algorithms for large networks, focusing on the tradeoff between approximation and efficiency for fundamental graph optimization problems. The project will integrate tools from diverse areas such as combinatorial optimization, probability theory, mathematical programming, and continuous optimization to model and address these algorithmic questions, and the project is expected to shed new light on related questions in these domains as well.