Loading...
Please wait, while we are loading the content...
Similar Documents
Approximation algorithms for single-minded envy-free profit-maximization problems with limited supply
| Content Provider | CiteSeerX |
|---|---|
| Author | Cheung, Maurice Swamy, Chaitanya |
| Abstract | We present the first polynomial-time approximation algorithms for single-minded envy-free profit-maximization problems [13] 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 α-approximation algorithm for the corresponding SWM problem as input and return a solution that achieves profit at least OPT /O(α · log umax), where OPT is the optimal value of the SWM problem, and umax is the maximum supply of an item. This immediately yields approximation guarantees of O ( √ m log umax) for the general single-minded envy-free problem; and O(log umax) for the tollbooth and highway problems [13], and the graph-vertex pricing problem [3] (α = 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(α · log umax) 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. 1. |
| File Format | |
| Journal | FOCS |
| Language | English |
| Access Restriction | Open |
| Subject Keyword | Limited Supply Single-minded Envy-free Profit-maximization Problem Approximation Algorithm Optimal Value Corresponding Swm Problem Envy-freeness Constraint Upper Bound Profit-maximization Problem Corresponding Social-welfare-maximization Maximum Profit Log Umax Optimum Value Highway Problem Non-envy-free Version Swm Problem Graph-vertex Pricing Problem General Single-minded Envy-free Problem Pricing Scheme First Polynomial-time Approximation Algorithm Optimum Profit Maximum Total Value Approximation Guarantee Lp-based Approximation Algorithm Maximum Supply |
| Content Type | Text |
| Resource Type | Article |
