Eva Tardos, Lectures 1 - 4



Approximation algorithms is becoming an increasingly developed area of research. A number of deep and elegant techniques have been developed, and each has been applied to a variety of problems. The first three of the talks will review three of the basic techniques: linear programming and rounding, local search, and primal-dual algorithms, and show a nice result illustrating each of the basic techniques. The forth talk will discuss issues arising from considering (approximation) algorithms from a game theoretical perspective.

The first talk will focus of the traditional classification problem, where we wish to assign one of k labels (or classes) to each of n objects, in a way that is consistent with some observed data that we have about the problem including pair-wise relationships among the objects to be classified. From the perspective of combinatorial optimization, this problem can be viewed as a generalization of certain graph partitioning problems, and equivalent to a type of computationally hard assignment problem. We will use the linear programming and rounding technique to give an approximation algorithm for this problem. This talk is based on joint work of Jon Kleinberg and myself.

In the second talk, we will focus on a local search technique. We will apply local search for some special cases of the above classification problem. Solving large linear programs is slow, and this points to the need of simpler combinatorial techniques. We will show that in some cases the simpler local search technique provides faster and better approximation results. This talk is based on work of Yuri Boykov, Olga Veksler, and Ramin Zabih; and joint work of Anupam Gupta and myself.

The third talk we will discuss the primal-dual method for approximation algorithms. The problem we focus on is a type of clustering problem, such as facility location and k-median. Primal-dual algorithms take ideas and intuition from linear programming, but result in simple, and fast combinatorial algorithms for the problems. This talk will be mostly based on work of Kamal Jain and Vijay Vazirani.

In the fourth talk we will depart the theme of techniques for approximation algorithms, and show a new application area of algorithms. Traditional algorithms design assumes that the problem is described by a single objective function. In a number of settings it is natural to consider algorithmic questions where multiple agents each pursue their own selfish interests. This perspective gives rise of a number of very interesting questions at the intersection of game theory and (approximation) algorithms. In this talk we will focus on what is the price of this "anarchy"? i.e., to what extend does the result of selfishness approximate an optimal centrally designed solution? This talk will be based on work of Tim Roughgarden and myself.

Back to the IPCO VIII Program.