Advanced search
Start date
Betweenand
Related content
(Reference retrieved automatically from Web of Science through information on FAPESP grant and its corresponding number as mentioned in the publication by the authors.)

Approximation Algorithms for the Max-Buying Problem with Limited Supply

Full text
Author(s):
Fernandes, Cristina G. [1] ; Schouery, Rafael C. S. [2]
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