{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,14]],"date-time":"2026-05-14T05:51:33Z","timestamp":1778737893658,"version":"3.51.4"},"reference-count":19,"publisher":"EDP Sciences","issue":"2","license":[{"start":{"date-parts":[[2019,6,5]],"date-time":"2019-06-05T00:00:00Z","timestamp":1559692800000},"content-version":"vor","delay-in-days":65,"URL":"https:\/\/www.edpsciences.org\/en\/authors\/copyright-and-licensing"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["RAIRO-Oper. Res."],"accepted":{"date-parts":[[2018,9,4]]},"published-print":{"date-parts":[[2019,4]]},"abstract":"<jats:p>In this work we investigate the<jats:italic>portfolio selection problem<\/jats:italic>(P1) and<jats:italic>bi-directional trading<\/jats:italic>(P2) when prices are interrelated. Zhang<jats:italic>et al.<\/jats:italic>(<jats:italic>J. Comb. Optim.<\/jats:italic><jats:bold>23<\/jats:bold>(2012) 159\u2013166) provided the algorithm UND which solves one variant of P2. We are interested in solutions which are optimal from a worst-case perspective. For P1, we prove the worst-case input sequence and derive the algorithm<jats:italic>optimal portfolio for interrelated prices<\/jats:italic>(OPIP). We then prove the competitive ratio and optimality. We use the idea of OPIP to solve P2 and derive the algorithm called<jats:italic>optimal conversion for interrelated prices<\/jats:italic>(OCIP). Using OCIP, we also design optimal online algorithms for<jats:italic>bi-directional search<\/jats:italic>(P3) called<jats:italic>bi-directional UND<\/jats:italic>(BUND) and<jats:italic>optimal online search for unknown relative price bounds<\/jats:italic>(RUN). We run numerical experiments and conclude that OPIP and OCIP perform well compared to other algorithms even if prices do not behave adverse.<\/jats:p>","DOI":"10.1051\/ro\/2018064","type":"journal-article","created":{"date-parts":[[2018,9,6]],"date-time":"2018-09-06T18:50:56Z","timestamp":1536259856000},"page":"559-576","source":"Crossref","is-referenced-by-count":11,"title":["Optimal online algorithms for the portfolio selection problem, bi-directional trading and -search with interrelated prices"],"prefix":"10.1051","volume":"53","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2483-8233","authenticated-orcid":false,"given":"Pascal","family":"Schroeder","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Imed","family":"Kacem","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"G\u00fcnter","family":"Schmidt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"250","published-online":{"date-parts":[[2019,6,5]]},"reference":[{"key":"R1","doi-asserted-by":"crossref","unstructured":"Agarwal A., Hazan E., Kale S. and Schapire R.E., Algorithms for portfolio management based on the newton method. In: Proceedings of the 23rd International Conference on Machine Learning. ACM (2006) 9\u201316.","DOI":"10.1145\/1143844.1143846"},{"key":"R2","doi-asserted-by":"crossref","first-page":"241","DOI":"10.1051\/ro\/2011114","volume":"45","author":"Boria","year":"2011","journal-title":"RAIRO: OR"},{"key":"R3","unstructured":"Borodin A., El-Yaniv R. and Gogan V., On the competitive theory and practice of portfolio selection (Extended Abstract). In: Proceedings of the 4th Latin American Symposium on Theoretical Informatics (2000) 173\u2013196."},{"key":"R4","first-page":"579","volume":"21","author":"Borodin","year":"2004","journal-title":"J. Artif. Intell. Res. AI Access Found."},{"key":"R5","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1137\/S0097539799358847","volume":"31","author":"Chen","year":"2001","journal-title":"SIAM J. Comput."},{"key":"R6","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1111\/j.1467-9965.1991.tb00002.x","volume":"1","author":"Cover","year":"1991","journal-title":"Math. Finance"},{"key":"R7","doi-asserted-by":"crossref","unstructured":"Dochow R., Online Algorithms for the Portfolio Selection Problem. Springer, Berlin (2016).","DOI":"10.1007\/978-3-658-13528-7"},{"key":"R8","doi-asserted-by":"crossref","first-page":"749","DOI":"10.1051\/ro\/2016030","volume":"50","author":"Gangolf","year":"2016","journal-title":"RAIRO: OR"},{"key":"R9","doi-asserted-by":"crossref","first-page":"325","DOI":"10.1111\/1467-9965.00058","volume":"8","author":"Helmbold","year":"1998","journal-title":"Math. Finance"},{"key":"R10","unstructured":"Huang D., Zhou J., Li B., Hoi S.C. and Zhou S., Robust median reversion strategy for on-line portfolio selection. In: Proceedings of the 23rd International Joint Conference on Artificial Intelligence (2013) 2006\u20132012."},{"key":"R11","first-page":"423","volume":"3","author":"Kalai","year":"2002","journal-title":"J. Mach. Learn. Res."},{"key":"R12","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/s10994-012-5281-z","volume":"87","author":"Li","year":"2012","journal-title":"Mach. Learn."},{"key":"R13","doi-asserted-by":"crossref","first-page":"1096","DOI":"10.1007\/s10878-017-0131-3","volume":"34","author":"Schmidt","year":"2017","journal-title":"J. Comb. Optim."},{"key":"R14","unstructured":"Schroeder P., Dochow R. and Schmidt G., Conversion algorithms with a reward function and interrelated conversion rates. In: Proceedings of the 45th International Conference on Computers and Industrial Engineering. France (2015) 536\u2013543."},{"key":"R15","unstructured":"Schroeder P. and Kacem I., Optimal cash management with uncertain and interrelated demands. In: Proceedings of the 47th International Conference on Computers and Industrial Engineering. Portugal (2017) 502\u2013508."},{"key":"R16","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1016\/j.cie.2018.03.034","volume":"119","author":"Schroeder","year":"2018","journal-title":"Comput. Ind. Eng."},{"key":"R17","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1145\/2786.2793","volume":"28","author":"Sleator","year":"1985","journal-title":"Commun. ACM"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"El-Yaniv R., Fiat A., Karp R. and Turpin G., competitive analysis of financial games. In: Proceedings of the 33rd Annual Symposium on Foundations of Computer Science (1992) 327\u2013333.","DOI":"10.1109\/SFCS.1992.267758"},{"key":"R19","doi-asserted-by":"crossref","first-page":"159","DOI":"10.1007\/s10878-010-9344-4","volume":"23","author":"Zhang","year":"2012","journal-title":"J. Comb. Optim."}],"container-title":["RAIRO - Operations Research"],"original-title":[],"link":[{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2018064\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,31]],"date-time":"2022-08-31T21:26:32Z","timestamp":1661981192000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.rairo-ro.org\/10.1051\/ro\/2018064"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,4]]},"references-count":19,"journal-issue":{"issue":"2"},"alternative-id":["ro180201"],"URL":"https:\/\/doi.org\/10.1051\/ro\/2018064","relation":{},"ISSN":["0399-0559","1290-3868"],"issn-type":[{"value":"0399-0559","type":"print"},{"value":"1290-3868","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,4]]}}}