Competitive Algorithms for Unbounded One-Way Trading
文献类型:会议论文
作者 | Chin, Francis Y. L.; Fu, Bin; Jiang, Minghui; Ting, Hing-Fung; Zhang, Yong |
出版日期 | 2014 |
会议名称 | 10th International Conference on Algorithmic Aspects of Information and Management, AAIM 2014 |
会议地点 | Vancouver, BC, Canada |
英文摘要 | In the one-way trading problem, a seller has some product to be sold to a sequence sigma of buyers u(1), u(2), ... , u(sigma) arriving online and he needs to decide, for each u(i), the amount of product to be sold to u(i) at the then-prevailing market price p(i). The objective is tomaximize the seller's revenue. We note that most 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. Moreover, the performance guarantees provided by these algorithms depend only on M and m, and are often too loose; for example, given a one-way trading algorithm with competitive ratio Theta(log(M/m)), its actual performance can be significantly better when the actual highest to actual lowest price ratio is significantly smaller than M/m. |
收录类别 | EI |
语种 | 英语 |
源URL | [http://ir.siat.ac.cn:8080/handle/172644/6023] |
专题 | 深圳先进技术研究院_数字所 |
作者单位 | 2014 |
推荐引用方式 GB/T 7714 | Chin, Francis Y. L.,Fu, Bin,Jiang, Minghui,et al. Competitive Algorithms for Unbounded One-Way Trading[C]. 见:10th International Conference on Algorithmic Aspects of Information and Management, AAIM 2014. Vancouver, BC, Canada. |
入库方式: OAI收割
来源:深圳先进技术研究院
浏览0
下载0
收藏0
其他版本
除非特别说明,本系统中所有内容都受版权保护,并保留所有权利。