A funcionalidade de pesquisa está em construção.
A funcionalidade de pesquisa está em construção.

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice

The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice

Bounds for the Multislope Ski-Rental Problem Limites para o problema do aluguel de esqui em múltiplas pistas

Hiroshi FUJIWARA, Kei SHIBUSAWA, Kouki YAMAMOTO, Hiroaki YAMAMOTO

  • Exibições de texto completo

    0

  • Cite isto

Resumo:

O problema do aluguel de esquis multipistas é um problema de otimização online que generaliza o problema clássico do aluguel de esquis. Ao jogador são oferecidas não apenas opções de compra e aluguel, mas também outras opções que cobram taxas iniciais e por tempo. Sabe-se que o rácio competitivo do problema clássico do aluguer de esquis é 2. Em contraste, o mais conhecido até agora sobre o rácio competitivo do problema do aluguer de esquis multipistas é um limite superior de 4 e um limite inferior de 3.62. Neste artigo consideramos uma versão paramétrica do problema de aluguel de esquis multipistas, tendo como parâmetro o número de opções. Provamos um limite superior para o problema paramétrico que é estritamente menor que 4. Além disso, fornecemos uma relação de recorrência simples que produz uma equação tendo um valor de limite inferior como raiz.

Publicação
IEICE TRANSACTIONS on Information Vol.E103-D No.3 pp.481-488
Data de publicação
2020/03/01
Publicitada
2019/11/25
ISSN online
1745-1361
DOI
10.1587/transinf.2019FCP0001
Tipo de Manuscrito
Special Section PAPER (Special Section on Foundations of Computer Science — Frontiers of Theory of Computation and Algorithm —)
Categoria

autores

Hiroshi FUJIWARA
  Shinshu University
Kei SHIBUSAWA
  Shinshu University
Kouki YAMAMOTO
  Shinshu University
Hiroaki YAMAMOTO
  Shinshu University

Palavra-chave