5 citations · 5 across the 1 of their papers we have counts for
5 papers
Online Unit Profit Knapsack with Untrusted Predictions
Joan Boyar, Lene M. Favrholdt, Kim S. Larsen
A variant of the online knapsack problem is considered in the settings of trusted and untrusted predictions. In Unit Profit Knapsack, the items have unit profit, and it is easy to…
Online Bin Covering with Advice
Joan Boyar, Lene M. Favrholdt, Shahin Kamali +1
The bin covering problem asks for covering a maximum number of bins with an online sequence of items of different sizes in the range ; a bin is said to be covered if it…
Advice Complexity of Priority Algorithms
Allan Borodin, Joan Boyar, Kim S. Larsen +1
The priority model of "greedy-like" algorithms was introduced by Borodin, Nielsen, and Rackoff in 2002. We augment this model by allowing priority algorithms to have access to advi…
The Scheduler is Very Powerful in Competitive Analysis of Distributed List Accessing
Joan Boyar, Faith Ellen, Kim S. Larsen
This work is a continuation of efforts to define and understand competitive analysis of algorithms in a distributed shared memory setting, which is surprisingly different from the…
Cancellation-free circuits: An approach for proving superlinear lower bounds for linear Boolean operators
Joan Boyar, Magnus Find
We continue to study the notion of cancellation-free linear circuits. We show that every matrix can be computed by a cancellation- free circuit, and almost all of these are at most…