Eastern Great Lakes Theory Workshop Talk

Approximation Algorithms for Single-Minded Envy-Free Profit-Maximization Problems with Limited Supply

Chaitanya Swamy, University of Waterloo

Saturday, September 7, 11:30 am- 12:30pm

ABSTRACT

We present the first polynomial-time approximation algorithms for single-minded envy-free profit-maximization problems (Guruswami et al.} with limited supply. Our algorithms return a pricing scheme and a subset of customers that are designated the winners, which satisfy the envy-freeness constraint, whereas in our analyses, we compare the profit of our solution against the optimal value of the corresponding social-welfare-maximization (SWM) problem of finding a winner-set with maximum total value. Our algorithms take any LP-based \rho-approximation algorithm for the corresponding SWM problem as input and return a solution that achieves profit at least OPT/O(\rho\log u_max), where OPT is the optimal value of the SWM problem, and u_max is the maximum supply of an item. This immediately yields approximation guarantees of O(\sqrt m\log u_max) for the general single-minded envy-free problem; and O(\log u_max) for the tollbooth problem, highway problem, and the graph-vertex pricing problem (\rho=O(1) for all the corresponding SWM problems). Since OPT is an upper bound on the maximum profit achievable by any solution (i.e., irrespective of whether the solution satisfies the envy-freeness constraint), our results directly carry over to the non-envy-free versions of these problems too. Our result also thus (constructively) establishes an upper bound of O(\rho\log u_max) on the ratio of (i) the optimum value of the profit-maximization problem and OPT; and (ii) the optimum profit achievable with and without the constraint of envy-freeness.

Slides

Speaker Bio

Chaitanya Swamy obtained his Ph.D. in Computer Science from Cornell University in 2004 under the supervision of David Shmoys. He spent two years as a postdoctoral scholar at Caltech, and is currently an assistant professor in the Combinatorics and Optimization department at the University of Waterloo.

His research interests center mainly around approximation algorithms, combinatorial optimization, and algorithmic game theory. An ongoing focus of his research is the development of provably good algorithms for planning under uncertainty.

< Schedule < EaGL homepage