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

Abstract

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
PublisherSpringer
Publication date2016
Pages203-212
ISBN (Print)978-3-319-44542-7
ISBN (Electronic)978-3-319-44543-4
DOIs
Publication statusPublished - 2016
Event27th International Workshop on Combinatorial Algorithms - Helsinki, Finland
Duration: 17. Aug 201619. Aug 2016

Conference

Conference27th International Workshop on Combinatorial Algorithms
CountryFinland
CityHelsinki
Period17/08/201619/08/2016
SeriesLecture Notes in Computer Science
Volume9843
ISSN0302-9743

Keywords

  • 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