Competitive algorithms for unbounded one-way trading
journal contributionposted on 10.07.2015, 15:27 authored by Francis Y.L. Chin, Bin Fu, Jiuling Guo, Shuguang Han, Jueliang Hu, Minghui Jiang, Guohui Lin, Hing-Fung Ting, Luping Zhang, Yong Zhang, Diwei ZhouDiwei Zhou
In the one-way trading problem, a seller has L units of product to be sold to a sequence σ of buyers u1,u2,…,uσ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/mM/m, at the outset....[cont'd]
This work is supported by NSFC (61433012, U1435215, 11171086), Natural Science Foundation of Hebei Province A2013201218, HK RGC grant HKU-711709E, HK RGC grant HKU-716412E.
- Mathematical Sciences