Course: Approximation algorithms for hard combinatorial problems and games

Take into account that during UPC Easter holydays there will be no sessions  (March 29 to April 5 both included)

Summary:
The course will present the basic concepts and techniques for approximating hard combinatorial problems. We'll specifically address the cases when the input data will entirely be known only in the future or it is private knowledge of independent players as it is customary in modern applications motivated by the Internet. We'll start by reviewing the basic concepts for the the approximation of hard combinatorial problems. We'll then introduce the techniques based on Linear Programming and the Primal-dual method and show its application to basic network design problems.

Primal-dual approximation algorithms have a natural interpretation as cost-sharing mechanisms. The dual variables can often be considered as costs that players or groups of players pay for constructing a good approximate or exact solution to a combinatorial problem. Very recently, this connection has been made even more explicit by casting the idea of cost-sharing in the analysis of a class of randomized approximation algorithms [Gupta, Kumar and Roughgarden 2003]. We'll introduce a class of facility location and rent-or-buy network design problems and show how a set of carefully designed cost shares allow to analyze in a simple and elegant way the performance guarantees of a wide class of randomized approximation algorithms.

A generalization of the basic randomized framework also finds applications to a class of stochastic optimization problems where uncertainty on data is modeled by a probability distribution over a number of alternative scenarios. We specifically present approximation algorithms for two-stage stochastic optimization in the black box model model [Gupta, Pal, Ravi and Sinha, 2004] for Steiner tree, facility location and vertex cover. Strict cost-shares are also used for the analysis of algorithms for on-line stochastic optimization. The input instance here is defined by a number of independent samples from a known distribution. The expected competitive ratio of algorithms for a number of network design optimization problems will be discussed [Garg, Gupta, L., Sankowski, 2008]. We conclude with a digression on algorithms for universal stochastic optimization. Universal optimization is to compute a solution that is good for all the input sequences. We consider the set cover problem where the universal algorithm produces an a-priori map from elements to sets [Grandoni, Gupta, L., Miettinen, Sankowski, Singh, 2008].

Cost-sharing methods have been originated in Economics since developing fair cost-haring methods is a central problem in cooperative game theory. We'll address the issues of the design of cost-sharing mechanisms that encourage truthful and fair behavior among users. We'll present mechanisms able to share in fair manner the cost of a network infrastructure with several connectivity requirements and objective functions. The mechanisms should satisfy at the same time several objectives as for instance truthfulness, cost recovery, social costs and be resilient against coalitions. These cost-sharing mechanisms take in general the form of primal-dual approximation algorithms. However, the truthfulness requirement imposes additional limitation to the approximation factors that can be achieved.

Finally we'll consider the approximation of hard combinatorial problems when the input data is private knowledge of independent selfish players. We cast this class of problems in the broad area of mechanism design. The dominant solution concept is the development of mechanisms/algorithms that define a solution and a set of payments such that every player is incentivized to reveal the truth values of the input data. The Vickrey-Clarke-Groves (VCG) mechanism provides a cornerstone method to design truthful algorithms. However, VCG is not computationally efficient for hard combinatorial problems. Alternative methods based on some monotonicity criteria have been proposed to design efficient truthful approximation algorithms and approximation schemes. We'll present the basic concepts for designing truthful mechanisms for single and multiple objective optimization.

Course Outline:
1. Introduction to approximation algorithms: simple examples, ptas, fptas, LP-based approximation (4 h)
2. Approximation algorithms for network design problems (4h)
3. Cost-sharing methods for approximation algorithms: rent-or-buy network design (4h)
4. Cost-sharing methods for stochastic optimization: approximation of 2-stage stochastic optimization and stochastic-online algorithms (4h)
5.Cost-sharing games and approximation: group strategy proof mechanisms (4h)
6. Mechanism design and approximation: VCG, Vickrey auction, monotone mechanisms, truthful approximation schemes (4h)
7. Research seminars:
          1) Truthful approximation schemes for multi criteria optimization;
          2) Auctions with budgets (3 h)
8. Assignment and discussion of homeworks (3 h).

Student work:
The students will be assigned exercises and additional readings on each topic of the course.
Evaluation of the course:
The evaluation of the course will be done through the assignment of three homeworks, respectively on topics 1-3, 4-5 and 6-7.
The course is open to any interested person, please send an e-mail to Mercè Juan (merce@lsi.upc.edu)confirming your participation.


For PhD or Master students it is possible to get additional ECTS credits for this course, please contact Mercè Juan(merce@lsi.upc.edu) indicating your situation.
The course is organized under the mobility program for professors in University Master degrees funded by the Spanish Ministry of Education.