Applications of cost-sharing methods to hard optimization problems

Stefano Leonardi 
Sapienza University of Rome 


Lecture 1. Cross-monotonic cost-sharing mechanisms for network design 

Cost-sharing methods have been originated in Economics since developing fair cost-haring methods is 
a central problem in cooperative game theory.  In this first lecture 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.

Topics: 

- Introduction to cost-sharing mechanisms: the multicast problem.
- Shapley cost-shares
- Cross-monotonic cost-shares
- Properties of cross-monotonic cost-shares
- The Steiner forest problem
- Cost-shares for Steiner forest
- A suitable LP relaxation for Steiner forest
- Lower bounds on cost recovery of cross-monotonic cost-shares 


Lecture 2.  Cost-sharing methods in approximation algorithms

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. 

Topics: 

Facility location problems. 
Primal-dual algorithms for facility location. 
Cross-monotonic Cost-shares for facility location
Rent-or-buy network design
Sample-augment algorithm 
Strict cost-shares and analysis of the algorithm
Strict cost-shares for Steiner Tree
Multi-commodity rent-or-buy network design
Strict cost-shares for Steiner forest

Lecture 3.  Cost-sharing methods for stochastic optimization

A generalization of the basic randomized framework  described in Lecture 2 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.  We construct universal mappings that achieve 
a logarithmic competitive ratio on inputs formed from independent samples of elements from a known 
distribution [Grandoni, Gupta, L., Miettinen, Sankowski, Singh, 2008]. 

Topics: 

Two-stage stochastic optimization
Boosted sampling
Applications
On-line stochastic optimization
Expected ration vs Ratio of Expectation
The on-line stochastic Steiner tree problem
Universal stochastic algorithms 
Unweighted set cover
Weighted set cover