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