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.