Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
On the Advice Complexity of Online Problems
ETH Zurich.
ETH Zurich.
Comenius University.
ETH Zurich.
Show others and affiliations
2009 (English)In: Algorithms and Computation: 20th International Symposium, ISAAC 2009, Honolulu, Hawaii, USA, December 16-18, 2009. Proceedings, Berlin: Springer Berlin/Heidelberg, 2009, Vol. 5878, 331-340 p.Conference paper, Published paper (Refereed)
Abstract [en]

In this paper, we investigate to what extent the solution quality of online algorithms can be improved by allowing the algorithm to extract a given amount of information about the input. We consider the recently introduced notion of advice complexity where the algorithm, in addition to being fed the requests one by one, has access to a tape of advice bits that were computed by some oracle function from the complete input. The advice complexity is the number of advice bits read. We introduce an improved model of advice complexity and investigate the connections of advice complexity to the competitive ratio of both deterministic and randomized online algorithms using the paging problem, job shop scheduling, and the routing problem on a line as sample problems. We provide both upper and lower bounds on the advice complexity of all three problems. Our results for all of these problems show that very small advice (only three bits in the case of paging) already suffices to significantly improve over the best deterministic algorithm. Moreover, to achieve the same competitive ratio as any randomized online algorithm, a logarithmic number of advice bits is sufficient. On the other hand, to obtain optimality, much larger advice is necessary.

Place, publisher, year, edition, pages
Berlin: Springer Berlin/Heidelberg, 2009. Vol. 5878, 331-340 p.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 5878
Keyword [en]
on-line algorithms, advice complexity
National Category
Computer Science
Identifiers
URN: urn:nbn:se:kth:diva-52378DOI: 10.1007/978-3-642-10631-6_35ISBN: 978-3-642-10630-9 (print)ISBN: 3642106307 (print)OAI: oai:DiVA.org:kth-52378DiVA: diva2:466349
Conference
20th International Symposium on Algorithms and Computation, ISAAC 2009; Honolulu, HI; 16 December 2009 through 18 December 2009
Projects
ETH grant TH 18 07-3APVV grant 0433-06
Note
QC 20120113Available from: 2011-12-15 Created: 2011-12-15 Last updated: 2012-01-13Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Mömke, Tobias
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
isbn
urn-nbn

Altmetric score

doi
isbn
urn-nbn
Total: 25 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf