Committee: Ambuj Singh (Chair), Amr El Abbadi, Xifeng Yan, Charu Aggarwal, Prithwish Basu
Title: Scalable Algorithms for Network Design
Abstract:
Networks (or graphs) are a powerful tool to model complex systems in many real-applications, such as those arising from social media, transportation, and communications. Often times, there is a need for modifying (e.g. dismantling, augmenting) a network in order to achieve a desired property. For instance, the diffusion of fake news can be contained via blocking some links in a social network. Similarly, drivers' commute time can be reduced by improving a few road intersections. Characterizing the combinatorial effect of these network modifications leads to interesting and challenging optimization problems and algorithms.

In this talk, I will present my work on optimizing shortest path distances and group centrality in large networks. More specifically, I will show how randomized algorithms can enable network design in several applications. While these algorithms are easy to implement, they often achieve good probabilistic approximation bounds. This is of key importance, as design problems are usually computationally harder than their search counterparts (e.g. shortest path or group centrality queries). My talk will also cover two new design problems in a different hardness spectra. In the influence minimization problem, we are able to provide efficient constant-factor approximations using submodular function optimization. On the other hand,  the k-core minimization problem does not admit such a constant factor approximation. I will finish with a discussion of potential solutions for these problems as part of my thesis.