The advice complexity of a class of hard online problems
type: Item
instance of: scholarly article
title: The advice complexity of a class of hard online problems
zbMATH Open document ID: 1387.68302
author: Christian Kudahl
author: Jesper W. Mikkelsen
author: Joan Boyar
author: Lene M. Favrholdt
published in: Theory of Computing Systems
publication date: 2018-02-01T00:00:00Z
Mathematics Subject Classification ID: 68W27
Mathematics Subject Classification ID: 68Q15
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 6833242
zbMATH Keywords: online algorithms
zbMATH Keywords: advice complexity
zbMATH Keywords: complexity class
zbMATH Keywords: asymmetric string guessing
zbMATH Keywords: covering designs
zbMATH Keywords: asymmetric online covering (AOC)
MaRDI profile type: Publication
full work available at URL: s00224-016-9688-y
OpenAlex ID: W1500425902
cites work: The Online Set Cover Problem
cites work: Tight Bounds for the Advice Complexity of the Online Minimum Steiner Tree Problem
cites work: On the Power of Advice and Randomization for the Disjoint Path Allocation Problem
cites work: Online coloring of bipartite graphs with and without advice
cites work: The string guessing problem as a method to prove lower bounds on the advice complexity
cites work: On the Advice Complexity of the k-Server Problem
cites work: On the Advice Complexity of Online Problems
cites work: The online knapsack problem: advice and randomization
cites work: On the list update problem with advice
cites work: Online bin packing with advice
cites work: On-line vertex-covering
cites work: Q4004080
cites work: Advice complexity of maximum independent set in sparse and bipartite graphs
cites work: Measuring the problem-relevant information in input
cites work: Online computation with advice
cites work: Q4065548
cites work: Advice Complexity of Online Coloring for Paths
cites work: On Advice Complexity of the k-server Problem under Sparse Metrics
cites work: Online independent sets.
cites work: Lower bounds for on-line graph coloring
cites work: Clique is hard to approximate within \(n^{1-\epsilon}\)
cites work: Information Complexity of Online Problems
cites work: Competitive snoopy caching
cites work: On the Advice Complexity of the Set Cover Problem
cites work: Stochastic on-line knapsack problems
cites work: Optimal Online Edge Coloring of Planar Graphs with Advice
cites work: Probability and Computing
cites work: On the advice complexity of online bipartite matching and online stable marriage
cites work: Q4527015
cites work: Online algorithms with advice for bin packing and scheduling problems
cites work: Advice Complexity of the Online Coloring Problem
DOI: 10.1007/S00224-016-9688-Y
description: scientific article; zbMATH DE number 6833242