| Full text | |
| Author(s): |
Total Authors: 2
|
| Affiliation: | [1] Univ Sao Paulo, Inst Matemat & Estat, Rua Matao, 1010, Cidade Univ, BR-05508090 Sao Paulo, SP - Brazil
[2] Univ Estadual Campinas, Inst Comp, Av Albert Einstein, 1251, Cidade Univ, BR-13083852 Campinas, SP - Brazil
Total Affiliations: 2
|
| Document type: | Journal article |
| Source: | ALGORITHMICA; v. 80, n. 11, p. 2973-2992, NOV 2018. |
| Web of Science Citations: | 0 |
| Abstract | |
We consider the Max-Buying Problem with Limited Supply, in which there are n items, with copies of each item i, and m consumers such that each consumer b has a valuation for item i. The goal is to find a pricing p and an allocation of items to consumers that maximize the revenue, with every item allocated to at most consumers, every consumer receives at most one item, and if a consumer b receives item i, then . We present a randomized -approximation for the Max-Buying Problem with Limited Supply and show how to derandomize it, improving the previously known upper bound of 2. The algorithm uses an integer programming formulation with an exponential number of variables to do a probabilistic rounding and it explores some structure of the problem that might be useful when developing approximations for other pricing problems. We also present a PTAS for the price ladder variant, in which the pricing must be non-increasing (that is, ), improving the previously known upper bound of 4. (AU) | |
| FAPESP's process: | 13/03447-6 - Combinatorial structures, optimization, and algorithms in theoretical Computer Science |
| Grantee: | Carlos Eduardo Ferreira |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 15/11937-9 - Investigation of hard problems from the algorithmic and structural stand points |
| Grantee: | Flávio Keidi Miyazawa |
| Support Opportunities: | Research Projects - Thematic Grants |
| FAPESP's process: | 13/21744-8 - Theoretical and Pratical Approaches to Packing Problems |
| Grantee: | Rafael Crivellari Saliba Schouery |
| Support Opportunities: | Scholarships in Brazil - Post-Doctoral |