Constant competitive algorithms for unbounded one-Way trading under monotone hazard rate
Autor: | Yong Zhang, Hing-Fung Ting, Francis Y. L. Chin, Francis C. M. Lau, Haisheng Tan |
---|---|
Rok vydání: | 2018 |
Předmět: |
TheoryofComputation_MISCELLANEOUS
Independent and identically distributed random variables Sequence Competitive analysis Unit price Measure (mathematics) Theoretical Computer Science Computational Mathematics Monotone polygon Computational Theory and Mathematics Artificial Intelligence Product (mathematics) ComputingMilieux_COMPUTERSANDSOCIETY Constant (mathematics) Algorithm Mathematics |
Zdroj: | Mathematical Foundations of Computing. 1:383-392 |
ISSN: | 2577-8838 |
DOI: | 10.3934/mfc.2018019 |
Popis: | In the one-way trading problem, a seller has some product to be sold to a sequence of buyers in an online fashion, i.e., buyers come one after another. Each buyer has the accepted unit price which is known to the seller on his arrival. To maximize the total revenue, the seller has to carefully decide the amount of products to be sold to each buyer at the then-prevailing prices. In this paper, we study the unbounded one-way trading, i.e., the highest unit price among all buyers is positive and unbounded. We assume that the highest prices of buyers follow some distribution with monotone hazard rate, which is a well-adopted assumption. We investigate two variants, (1) the distribution is on the highest price among all buyers, and (2) the distribution of the highest price of each buyer is independent and identically distributed. To measure the performance of the algorithms, the expected competitive ratios, \begin{document}$ \mathrm{E}[OPT]/\mathrm{E}[ALG] $\end{document} and \begin{document}$ \mathrm{E}[OPT/ALG] $\end{document} , are considered. If the distributions satisfy the monotone hazard rate, for both of the above two variants, constant-competitive algorithms can be achieved. |
Databáze: | OpenAIRE |
Externí odkaz: | |
Nepřihlášeným uživatelům se plný text nezobrazuje | K zobrazení výsledku je třeba se přihlásit. |