Competitive Algorithms for Unbounded One-Way Trading
文献类型：期刊论文
| 作者 | Francis Y. L. Chin; Bin Fu; Jiuling Guo; Shuguang Han; Jueliang Hu; Minghui Jiang; Guohui Lin; Hing-Fung Ting; Luping Zhang; Yong Zhang |
| 刊名 | Theoretical Computer Science
 |
| 出版日期 | 2015 |
| 英文摘要 | In the one-way trading problem, a seller has L units of product to be sold to a sequence σ of buyers u1, u2, . . . , uσ arriving online and he needs to decide, for each ui , the amount of product to be sold to ui at the then-prevailing market price pi . The objective is to maximize the seller’s revenue. We note that all previous algorithms for the problem need to impose some artificial upper bound M and lower bound m on the market prices, and the seller needs to know either the values of M and m, or their ratio M/m, at the outset. This paper gives a one-way trading algorithm that does not impose any bounds on market prices and whose performance guarantee depends directly on the input. In particular, we give a class of one-way trading algorithms such that for any positive integer h and any positive number ϵ, we have an algorithm Ah,ϵ that has competitive ratio O(log r∗(log(2) r∗) . . . (log(h−1) r∗)(log(h) r∗)1+ϵ ) if the value of r∗ = p∗/p1, the ratio of the highest market price p∗ = maxi pi and the first price p1, is large and satisfies log(h) r∗ > 1, where log(i) x denotes the application of the logarithm function i times to x; otherwise, Ah,ϵ has a constant competitive ratio #h. We also show that our algorithms are near optimal by showing that given any positive integer h and any oneway trading algorithm A, we can construct a sequence of buyers σ with log(h) r∗ > 1 such that the ratio between the optimal revenue and the revenue obtained by A is $(log r∗(log(2) r∗) . . . (log(h−1) r∗)(log(h) r∗)). A special case of the one-way trading is also studied, in which the L units of product are comprised of L items, each of which must be sold atomically (or equivalently, the amount of product sold to each buyer must be an integer). Furthermore, a complementary problem to the one-way trading problem, say, the one-way buying problem, is studied in this paper. In the one-way buying problem, a buyer wants to purchase one unit of product through a sequence of n sellers v1, v2, . . . , vn arriving online, and she needs to decide the fraction to purchase from each vi at the then-prevailing market price pi . Her objective is to minimize the cost. The optimal competitive algorithms whose performance guarantees depend only on the lowest market price p∗ = mini pi , and one of M and ϕ, the price fluctuation ratio, are presented. |
| 收录类别 | SCI |
| 原文出处 | http://www.sciencedirect.com/science/article/pii/S0304397515004752 |
| 语种 | 英语 |
| WOS记录号 | WOS:000366773400004 |
| 源URL | [http://ir.siat.ac.cn:8080/handle/172644/6852]  |
| 专题 | 深圳先进技术研究院_数字所 |
| 作者单位 | Theoretical Computer Science |
| 推荐引用方式 GB/T 7714 | Francis Y. L. Chin,Bin Fu,Jiuling Guo,et al. Competitive Algorithms for Unbounded One-Way Trading[J]. Theoretical Computer Science,2015. |
| APA | Francis Y. L. Chin.,Bin Fu.,Jiuling Guo.,Shuguang Han.,Jueliang Hu.,...&Diwei Zhou.(2015).Competitive Algorithms for Unbounded One-Way Trading.Theoretical Computer Science. |
| MLA | Francis Y. L. Chin,et al."Competitive Algorithms for Unbounded One-Way Trading".Theoretical Computer Science (2015). |
入库方式： OAI收割
来源：深圳先进技术研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。