File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
 Publisher Website: 10.1007/9783319079561_4
 Scopus: eid_2s2.084903977446
 Find via
Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Conference Paper: Competitive algorithms for unbounded OneWay Trading
Title  Competitive algorithms for unbounded OneWay Trading 

Authors  
Issue Date  2014 
Publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ 
Citation  The 10th International Conference on Algorithmic Aspects of Information and Management (AAIM 2014), Vancouver, BC., Canada, 811 July 2014. In Lecture Notes in Computer Science, 2014, v. 8546, p. 3243 How to Cite? 
Abstract  In the oneway trading problem, a seller has some 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 thenprevailing market price pi. The objective is to maximize 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 oneway trading algorithm with competitive ratio Θ(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. This paper gives a oneway 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 oneway trading algorithms such that for any positive integer h and any positive number ε, we have an algorithm Ah,ε that has competitive ratio O (logr*(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 satisfy 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 at least Ω(logr*(log(2) r*) ... (log(h  1) r*) (log(h) r*)). © 2014 Springer International Publishing. 
Description  LNCS v. 8546 entitled: Algorithmic aspects in information and management : 10th International Conference, AAIM 2014 ... proceedings 
Persistent Identifier  http://hdl.handle.net/10722/205524 
ISBN  
ISSN  2005 Impact Factor: 0.302 2015 SCImago Journal Rankings: 0.252 
DC Field  Value  Language 

dc.contributor.author  Chin, FYL  en_US 
dc.contributor.author  Fu, B  en_US 
dc.contributor.author  Jiang, MH  en_US 
dc.contributor.author  Ting, HF  en_US 
dc.contributor.author  Zhang, Y  en_US 
dc.date.accessioned  20140920T03:33:26Z   
dc.date.available  20140920T03:33:26Z   
dc.date.issued  2014  en_US 
dc.identifier.citation  The 10th International Conference on Algorithmic Aspects of Information and Management (AAIM 2014), Vancouver, BC., Canada, 811 July 2014. In Lecture Notes in Computer Science, 2014, v. 8546, p. 3243  en_US 
dc.identifier.isbn  9783319079554   
dc.identifier.issn  03029743   
dc.identifier.uri  http://hdl.handle.net/10722/205524   
dc.description  LNCS v. 8546 entitled: Algorithmic aspects in information and management : 10th International Conference, AAIM 2014 ... proceedings   
dc.description.abstract  In the oneway trading problem, a seller has some 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 thenprevailing market price pi. The objective is to maximize 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 oneway trading algorithm with competitive ratio Θ(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. This paper gives a oneway 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 oneway trading algorithms such that for any positive integer h and any positive number ε, we have an algorithm Ah,ε that has competitive ratio O (logr*(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 satisfy 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 at least Ω(logr*(log(2) r*) ... (log(h  1) r*) (log(h) r*)). © 2014 Springer International Publishing.   
dc.language  eng  en_US 
dc.publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/   
dc.relation.ispartof  Lecture Notes in Computer Science  en_US 
dc.rights  The original publication is available at www.springerlink.com   
dc.title  Competitive algorithms for unbounded OneWay Trading  en_US 
dc.type  Conference_Paper  en_US 
dc.identifier.email  Chin, FYL: chin@cs.hku.hk  en_US 
dc.identifier.email  Ting, HF: hfting@cs.hku.hk  en_US 
dc.identifier.email  Zhang, Y: yongzh@hku.hk  en_US 
dc.identifier.authority  Chin, FYL=rp00105  en_US 
dc.identifier.authority  Ting, HF=rp00177  en_US 
dc.identifier.doi  10.1007/9783319079561_4   
dc.identifier.scopus  eid_2s2.084903977446   
dc.identifier.hkuros  237898  en_US 
dc.identifier.volume  8546   
dc.identifier.spage  32   
dc.identifier.epage  43   
dc.publisher.place  Germany   
dc.customcontrol.immutable  sml 141208   