6 papers
Set Similarity Search for Skewed Data
Samuel McCauley, Jesper W. Mikkelsen, Rasmus Pagh
Set similarity join, as well as the corresponding indexing problem set similarity search, are fundamental primitives for managing noisy or uncertain data. For example, these primit…
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…
Randomization can be as helpful as a glimpse of the future in online computation
Jesper W. Mikkelsen
We provide simple but surprisingly useful direct product theorems for proving lower bounds on online algorithms with a limited amount of advice about the future. As a consequence,…
Optimal Online Edge Coloring of Planar Graphs with Advice
Jesper W. Mikkelsen
Using the framework of advice complexity, we study the amount of knowledge about the future that an online algorithm needs to color the edges of a graph optimally, i.e., using as f…
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…
Online Edge Coloring of Paths and Trees with a Fixed Number of Colors
Lene M. Favrholdt, Jesper W. Mikkelsen
We study a version of online edge coloring, where the goal is to color as many edges as possible using only a given number, , of available colors. All of our results are with re…