Busca avançada
Ano de início
Entree
(Referência obtida automaticamente do Web of Science, por meio da informação sobre o financiamento pela FAPESP e o número do processo correspondente, incluída na publicação pelos autores.)

Approximation Algorithms for the Max-Buying Problem with Limited Supply

Texto completo
Autor(es):
Fernandes, Cristina G. [1] ; Schouery, Rafael C. S. [2]
Número total de Autores: 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
Número total de Afiliações: 2
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
Linha de fomento: 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
Linha de fomento: 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
Linha de fomento: Bolsas no Brasil - Pós-Doutorado