Approximation Algorithms for the Max-Buying Problem with Limited Supply

Autor(es)

Fernandes, Cristina G. ^[1] ; Schouery, Rafael C. S. ^[2]

Afiliação do(s) autor(es)

^[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

• Tipo de documento: Artigo Científico
• Fonte: ALGORITHMICA; v. 80, n. 11, p. 2973-2992, NOV 2018.
• Citações Web of Science: 0

Resumo

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)

• Processo FAPESP: 13/03447-6 - Estruturas combinatórias, otimização e algoritmos em Teoria da Computação
• Beneficiário: Carlos Eduardo Ferreira
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 15/11937-9 - Investigação de problemas difíceis do ponto de vista algorítmico e estrutural
• Beneficiário: Flávio Keidi Miyazawa
• Modalidade de apoio: Auxílio à Pesquisa - Temático
• Processo FAPESP: 13/21744-8 - Abordagens Teóricas e Práticas para Problemas de Empacotamento
• Beneficiário: Rafael Crivellari Saliba Schouery
• Modalidade de apoio: Bolsas no Brasil - Pós-Doutorado