Speakers & Topics

Prof. C. Pandu Rangan, IIT, Chennai

Design Techniques for Approximation Algorithms: We will present an introduction to the basic design and analysis techniques for approximation algorithms. We begin with greedy technique and move on to examine local search methodology.   We conclude by discussing LP based methods and rounding techniques. We illustrate each technique with an interesting case study and give complete details of analysis. This will help first-time audience to get the much needed introduction to follow subsequent advanced talks.

Prof. Naveen Garg, IIT Delhi
Prof. R. Ravi, Carnegie Mellon University

Network Design - Exact and Approximate Solution Approaches: Profs. Garg and Ravi will present basic material in network optimization focusing on network design problems, their formulation as mathematical programs and in the case of hard problems, their approximability.

Prof. Garg will cover over the following over first day: linear programming duality, example of bipartite matchings; primal-dual algorithm for steiner forest, prize collecting Steiner tree and k-mst (introducing the idea of Lagrange relaxation); If time permits, he will touch upon Lovasz's splitting off theorem, Edmond's disjoint branching theorem & approximating k-edge connected subgraphs.

Prof. Ravi will cover the following over the second day: Iterative methods in combinatorial optimization focusing on assignment, spanning trees, matroids and their generalizations.

Prof. Philip Klein, Brown University

Optimization in Planar Networks: Prof. Klein will focus on structured networks, particularly on planar graphs. In the past five years, new algorithmic techniques have been developed for quickly finding optimal solutions and near-optimal solutions to optimization problems in planar graphs. Examples include maximum flow and minimum cut, traveling salesman, Steiner tree and Steiner forest, and shortest paths, and Prof. Klein will cover these techniques.

Prof. Aravind Srinivasan, University of Maryland

Randomization in Network Analysis: Prof. Srinivasan will focus on the various uses of randomization in the design and analysis of algorithms for network optimization, as well as in the analysis of large-scale network phenomena. After covering some basic topics, he will focus on recent developments in two areas:

(i) connections between random graphs (which often serve as good models for real-world networks) and statistical physics, and 

(ii) large-deviation bounds to analyze randomized algorithms.

Prof. Ravi Sundaram, Northeastern University

Network Security: Prof. Sudaram will focus on security in computer networks in conjunction with cryptography. He will provide a survey of both principles and practice along with in-depth tutorials on selected topics.

Prof. Rajmohan Rajaraman, Northeastern University

Diffusion in Networks: This tutorial will concern diffusion processes in large networks. Topics covered will include a subset of spectral graph theory, branching processes, the so-called small-world phenomena, and percolation theory. Time-permitting, we will also go over the challenges in modeling and analyzing dynamic networks.