"Iterative Methods in Combinatorial Optimization"

November 19 - December 5, 2008, (6 lectures)
RIMS, Kyoto University, Japan

Schedule of Lectures (updated on Nov. 8)

Abstract

     In this series of six lectures, I will describe a simple iterative method that supplies new proofs for a variety of exact results in combinatorial optimization. It is inspired by Jain's iterative rounding method for designing approximation algorithms for survivable network design problems, and augmented with a relaxation idea in the work of Lau, Naor, Salvatipour and Singh in their work on designing the approximation algorithm for its degree bounded version. Its application was further refined in recent work of Bansal, Khandekar and Nagarajan on degree-bounded directed network design.

     In lecture 1, I will review the background material on LP relaxations and their solvability and properties of extreme point or vertex solutions to such problems. I will then introduce the basic framework of the method using the assignment problem, and show its application by re-deriving the approximation results of Shmoys and Tardos for the generalized assignment problem.
     In lecture 2, I will discuss linear characterizations for the spanning tree polyhedron in undirected and directed graphs and give a new proof of their integrality using an iterative method. I will then illustrate an application to approximating the degree-bounded version of the undirected problem, by proving the results of Goemans and Lau & Singh.
     In lecture 3, I will discuss linear characterizations for the polyhedron of incidence vectors of matroid bases, as well as those of common bases of two matroids. If time permits, I will illustrate an application of the proof technique to approximation algorithms for a degree bounded version of the problem for binary matroids, showing a result of Kiraly, Lau & Singh.
     In lecture 4, I will discuss linear characterizations for the polyhedron of incidence vectors of submodular flows. If time permits, I will illustrate an application of the proof technique to approximation algorithms for a degree bounded version of the problem, also due to Kiraly et al.
     In lecture 5, I will discuss the linear characterization of the incidence vectors of perfect matchings in a general graph, as well as the integrality of solutions to systems with network matrices as constraints and integral right hand sides. Both of these will give new proofs using the iterative paradigm. If time permits, I will also discuss the integrality for some dual polyhedra (such as bipartite vertex cover and the dual of maximum weight basis of a matroid).
     Finally, in lecture 6, I will close with applications of the iterative method by revisiting Jain's original proof for the SNDP and giving a new proof that unifies its treatment with that for the Symmetric TSP polyhedron (describing joint work with Nagarajan and Singh). I will also illustrate other applications of the iterative method for designing approximation algorithms for a partial covering variant of vertex cover, multicriteria versions of minimum spanning tree (joint work with Grandoni and Singh), and a new proof of a theorem of Beck and Fiala in bounding the discrepancy of any edge in a bicoloring of a hypergraph by a function of its maximum degree.

     I plan to distribute drafts of relevant chapters from a monograph that I am co-authoring with Lap-Chi Lau and Mohit Singh during the lectures, and welcome feedback on them.

Access to RIMS
see the access information page of RIMS.

Link
R. Ravi (his web page)

Contact

Satoru Iwata
E-mail: iwata@kurims.kyoto-u.ac.jp
Research Institute for Mathematical Sciences, Kyoto University, Kyoto 606-8502, Japan