Advice Complexity of the Online Search Problem

Jhoirene Clemente, Juraj Hromkovič, Dennis Komm, Christian Kudahl

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review


The online search problem is a fundamental problem in finance. The numerous
direct applications include searching for optimal prices for commodity trading
and trading foreign currencies. In this paper, we analyze the advice
complexity of this problem.
In particular, we are interested in identifying the minimum amount of information needed in order to achieve a certain competitive ratio.
We design an algorithm that reads $b$ bits of advice and achieves a
competitive ratio of (M/m)^{1/(2^b+1)} where M and m are the maximum and
minimum price in the input. We also give a matching lower bound.
Furthermore, we compare the power of advice and randomization for this problem.
Original languageEnglish
Title of host publicationCombinatorial Algorithms : 27th International Workshop, IWOCA 2016, Helsinki, Finland, August 17-19, 2016, Proceedings
EditorsVeli Mäkinen, Simon J. Puglisi, Leena Salmela
Publication date2016
ISBN (Print)978-3-319-44542-7
ISBN (Electronic)978-3-319-44543-4
Publication statusPublished - 2016
Event27th International Workshop on Combinatorial Algorithms - Helsinki, Finland
Duration: 17. Aug 201619. Aug 2016


Conference27th International Workshop on Combinatorial Algorithms
SeriesLecture Notes in Computer Science


  • online algorithms
  • advice complexity

Fingerprint Dive into the research topics of 'Advice Complexity of the Online Search Problem'. Together they form a unique fingerprint.

Cite this