Random Structures and Algorithms

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

In this project the PI will study various properties of random graphs/networks. Such objects arise frequently in economics, such as transport networks, as models of social media platforms and even as the relations between proteins in animal cells. These networks are highly complex and are best modelled as if they have been randomly constructed. Typically, there are computational problems associated with such structures. For example in routing trucks one is faced with the problem of finding routes that minimize some objective. The PI will study such problems within a stochastic framework. Graduate students and postdocs will be involved in the project. The PI will study the typical structure of combinatorial objects. He will study random graphs and hypergraphs and determine thresholds for the existence of various properties. There are still many unanswered questions about Matchings, Hamilton cycles and Spanning Trees in this context and the PI will seek to answer some of them. This will involve questions where the edges have weights and colors. The PI will also consider the algorithmic questions that arise if one wants to find algorithms that work well in the average case. In some sense, this is an attempt to explain why NP-completeness is not necessarily a barrier to obtaining results in practice. In particular, the PI will study the expected performance of branch and bound algorithms, one of the most successful general approaches to hard problems. Finally, he will study combinatorial games that arise: usually Maker-Breaker games where Breaker tries to foil Maker's attempts at achieving some objective. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.