File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Competitive algorithms for unbounded One-Way Trading

TitleCompetitive algorithms for unbounded One-Way Trading
Authors
Issue Date2014
PublisherSpringer 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, 8-11 July 2014. In Lecture Notes in Computer Science, 2014, v. 8546, p. 32-43 How to Cite?
AbstractIn the one-way 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 then-prevailing 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 one-way 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 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 (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 one-way 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.
DescriptionLNCS v. 8546 entitled: Algorithmic aspects in information and management : 10th International Conference, AAIM 2014 ... proceedings
Persistent Identifierhttp://hdl.handle.net/10722/205524
ISBN
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252

 

DC FieldValueLanguage
dc.contributor.authorChin, FYLen_US
dc.contributor.authorFu, Ben_US
dc.contributor.authorJiang, MHen_US
dc.contributor.authorTing, HFen_US
dc.contributor.authorZhang, Yen_US
dc.date.accessioned2014-09-20T03:33:26Z-
dc.date.available2014-09-20T03:33:26Z-
dc.date.issued2014en_US
dc.identifier.citationThe 10th International Conference on Algorithmic Aspects of Information and Management (AAIM 2014), Vancouver, BC., Canada, 8-11 July 2014. In Lecture Notes in Computer Science, 2014, v. 8546, p. 32-43en_US
dc.identifier.isbn978-331907955-4-
dc.identifier.issn0302-9743-
dc.identifier.urihttp://hdl.handle.net/10722/205524-
dc.descriptionLNCS v. 8546 entitled: Algorithmic aspects in information and management : 10th International Conference, AAIM 2014 ... proceedings-
dc.description.abstractIn the one-way 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 then-prevailing 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 one-way 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 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 (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 one-way 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.languageengen_US
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/-
dc.relation.ispartofLecture Notes in Computer Scienceen_US
dc.rightsThe original publication is available at www.springerlink.com-
dc.titleCompetitive algorithms for unbounded One-Way Tradingen_US
dc.typeConference_Paperen_US
dc.identifier.emailChin, FYL: chin@cs.hku.hken_US
dc.identifier.emailTing, HF: hfting@cs.hku.hken_US
dc.identifier.emailZhang, Y: yongzh@hku.hken_US
dc.identifier.authorityChin, FYL=rp00105en_US
dc.identifier.authorityTing, HF=rp00177en_US
dc.identifier.doi10.1007/978-3-319-07956-1_4-
dc.identifier.scopuseid_2-s2.0-84903977446-
dc.identifier.hkuros237898en_US
dc.identifier.volume8546-
dc.identifier.spage32-
dc.identifier.epage43-
dc.publisher.placeGermany-
dc.customcontrol.immutablesml 141208-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats