The Advice Complexity of a Class of Hard Online Problems
- 1 August 2016
- journal article
- research article
- Published by Springer Nature in Theory of Computing Systems
- Vol. 61 (4) , 1128-1177
Abstract
No abstract availableKeywords
All Related Versions
Funding Information
- Villum Fonden (DK) (VKR023219)
- Det Frie Forskningsråd (DK) (DFF – 1323-00247)
This publication has 21 references indexed in Scilit:
- Online Coloring of Bipartite Graphs with and without AdviceAlgorithmica, 2013
- Online computation with adviceTheoretical Computer Science, 2011
- Measuring the problem-relevant information in inputRAIRO - Theoretical Informatics and Applications, 2009
- The Online Set Cover ProblemSIAM Journal on Computing, 2009
- On-line vertex-coveringTheoretical Computer Science, 2005
- Online independent setsTheoretical Computer Science, 2002
- Clique is hard to approximate within n1−εActa Mathematica, 1999
- Lower bounds for on-line graph coloringTheoretical Computer Science, 1994
- Competitive snoopy cachingAlgorithmica, 1988
- Amortized efficiency of list update and paging rulesCommunications of the ACM, 1985