15 citations · 31 across the 21 of their papers we have counts for
4 papers · 1 filter
On the List Update Problem with Advice
Joan Boyar, Shahin Kamali, Kim S. Larsen +1
We study the online list update problem under the advice model of computation. Under this model, an online algorithm receives partial information about the unknown parts of the inp…
Online Bin Covering: Expectations vs. Guarantees
Marie G. Christ, Lene M. Favrholdt, Kim S. Larsen
Bin covering is a dual version of classic bin packing. Thus, the goal is to cover as many bins as possible, where covering a bin means packing items of total size at least one in t…
The Frequent Items Problem in Online Streaming under Various Performance Measures
Joan Boyar, Kim S. Larsen, Abyayananda Maiti
In this paper, we strengthen the competitive analysis results obtained for a fundamental online streaming problem, the Frequent Items Problem. Additionally, we contribute with a mo…
Relative Interval Analysis of Paging Algorithms on Access Graphs
Joan Boyar, Sushmita Gupta, Kim S. Larsen
Access graphs, which have been used previously in connection with competitive analysis and relative worst order analysis to model locality of reference in paging, are considered in…