15 citations · 31 across the 21 of their papers we have counts for
25 papers
Online Minimum Spanning Trees with Weight Predictions
Magnus Berg, Joan Boyar, Lene M. Favrholdt +1
We consider the minimum spanning tree problem with predictions, using the weight-arrival model, i.e., the graph is given, together with predictions for the weights of all edges. Th…
Online Interval Scheduling with Predictions
Joan Boyar, Lene M. Favrholdt, Shahin Kamali +1
In online interval scheduling, the input is an online sequence of intervals, and the goal is to accept a maximum number of non-overlapping intervals. In the more general disjoint p…
Quotable Signatures for Authenticating Shared Quotes
Joan Boyar, Simon Erfurth, Kim S. Larsen +1
Quotable signature schemes are digital signature schemes with the additional property that from the signature for a message, any party can extract signatures for (allowable) quotes…
Product Portfolio Management in Competitive Environments
Samira Hossein Ghorban, Bardyaa Hesaam
Product diversity is one of the prominent factors for customers' satisfaction, while from the firms' perspective, the additional engineering costs required for product diversity sh…
Implementing Choreography Extraction
Luis Cruz-Filipe, Kim S. Larsen, Fabrizio Montesi +1
Choreographies are global descriptions of interactions among concurrent components, most notably used in the settings of verification and synthesis of correct-by-construction softw…
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…
Advice Complexity of Adaptive Priority Algorithms
Joan Boyar, Kim S. Larsen, Denis Pankratov
The priority model was introduced to capture "greedy-like" algorithms. Motivated by the success of advice complexity in the area of online algorithms, the fixed priority model was…
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…
Relaxing the Irrevocability Requirement for Online Graph Algorithms
Joan Boyar, Lene M. Favrholdt, Kim S. Larsen +1
Online graph problems are considered in models where the irrevocability requirement is relaxed. Motivated by practical examples where, for example, there is a cost associated with…
Batch Coloring of Graphs
Joan Boyar, Leah Epstein, Lene M. Favrholdt +2
In graph coloring problems, the goal is to assign a positive integer color to each vertex of an input graph such that adjacent vertices do not receive the same color assignment. Fo…
The Paths to Choreography Extraction
Luís Cruz-Filipe, Kim S. Larsen, Fabrizio Montesi
Choreographies are global descriptions of interactions among concurrent components, most notably used in the settings of verification (e.g., Multiparty Session Types) and synthesis…
Online Dominating Set
Joan Boyar, Stephan J. Eidenbenz, Lene M. Favrholdt +2
This paper is devoted to the online dominating set problem and its variants. We believe the paper represents the first systematic study of the effect of two limitations of online a…
Online Bounded Analysis
Joan Boyar, Leah Epstein, Lene M. Favrholdt +2
Though competitive analysis is often a very good tool for the analysis of online algorithms, sometimes it does not give any insight and sometimes it gives counter-intuitive results…
Online Multi-Coloring with Advice
Marie G. Christ, Lene M. Favrholdt, Kim S. Larsen
We consider the problem of online graph multi-coloring with advice. Multi-coloring is often used to model frequency allocation in cellular networks. We give several nearly tight up…
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…
Online Bin Packing with Advice
Joan Boyar, Shahin Kamali, Kim S. Larsen +1
We consider the online bin packing problem under the advice complexity model where the 'online constraint' is relaxed and an algorithm receives partial information about the future…
Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis
Joan Boyar, Sushmita Gupta, Kim S. Larsen
Access graphs, which have been used previously in connection with competitive analysis to model locality of reference in paging, are considered in connection with relative worst or…
A Comparison of Performance Measures via Online Search
Joan Boyar, Kim S. Larsen, Abyayananda Maiti
Though competitive analysis has been a very useful performance measure for the quality of online algorithms, it is recognized that it sometimes fails to distinguish between algorit…
List Factoring and Relative Worst Order Analysis
Martin R. Ehmsen, Jens S. Kohrt, Kim S. Larsen
Relative worst order analysis is a supplement or alternative to competitive analysis which has been shown to give results more in accordance with observed behavior of online algori…