Optimization Problems in Network Connectivity

  • Debmalya Panigrahi | MIT

Besides being one of the principal driving forces behind research in algorithmic theory for more than five decades, combinatorial optimization in graphs has assumed increased significance in recent times with the advent and large-scale use of a variety of real-life networks including communication networks connecting network elements, social and information networks connecting individuals and communities, and conceptual networks such as overlays. A fundamental objective in the study of such networks is to identify vulnerabilities in existing networks, and to design new networks that achieve desired robustness at minimum cost. This constitutes the area of graph connectivity algorithms. In this talk, I will give an overview of my contributions to this area of algorithmic research, focusing on the problems of graph sparsification (STOC ’11), minimum cuts (SODA ’09, SODA’08, STOC ’07, SODA ’07), and survivable network design (FOCS ’11, SODA ’11). The talk will be self-contained.

Speaker Details

Debmalya Panigrahi is a graduate student in the theory of computation group at CSAIL, MIT, where he is advised by Prof. David Karger. His research interests lie in algorithms, particularly for fundamental combinatorial problems in graphs, resource allocation problems, and online and stochastic optimization. Debmalya is also interested in algorithmic problems in other branches of computer science such as social, information, and communication networks, distributed systems, and databases. Before coming to MIT, he obtained a masters’ degree in computer science from the Indian Institute of Science.

    • Portrait of Debmalya Panigrahi

      Debmalya Panigrahi

    • Portrait of Jeff Running

      Jeff Running

Series: Microsoft Research Talks