1 citations · 1 across the 5 of their papers we have counts for
6 papers
Advice Complexity of the Online Search Problem
Jhoirene Clemente, Juraj Hromkovic, Dennis Komm +1
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 curre…
Weighted Online Problems with Advice
Joan Boyar, Lene M. Favrholdt, Christian Kudahl +1
Recently, the first online complexity class, AOC, was introduced. The class consists of many online problems where each request must be either accepted or rejected, and the aim is…
Advice Complexity of the Online Induced Subgraph Problem
Dennis Komm, Rastislav Královič, Richard Královič +1
Several well-studied graph problems aim to select a largest (or smallest) induced subgraph with a given property of the input graph. Examples of such problems include maximum indep…
Adding Isolated Vertices Makes some Online Algorithms Optimal
Joan Boyar, Christian Kudahl
An unexpected difference between online and offline algorithms is observed. The natural greedy algorithms are shown to be worst case online optimal for Online Independent Set and O…
The Advice Complexity of a Class of Hard Online Problems
Joan Boyar, Lene M. Favrholdt, Christian Kudahl +1
The advice complexity of an online problem is a measure of how much knowledge of the future an online algorithm needs in order to achieve a certain competitive ratio. Using advice…
Deciding the On-line Chromatic Number of a Graph with Pre-Coloring is PSPACE-Complete
Christian Kudahl
The problem of determining if the on-line chromatic number of a graph is less than or equal to k, given a pre-coloring, is shown to be PSPACE-complete.