8 citations · 25 across the 28 of their papers we have counts for
32 papers
On the Online Weighted Non-Crossing Matching Problem
Joan Boyar, Shahin Kamali, Kim S. Larsen +3
We introduce and study the weighted version of an online matching problem in the Euclidean plane with non-crossing constraints: points with non-negative weights arrive online, and…
Forwarding Packets Greedily on the Line
Joan Boyar, Lene M. Favrholdt, Kim S. Larsen +2
We consider the problem of forwarding packets arriving online with their destinations in a line network. In each time step, each router can forward one packet along the edge to its…
Distributed Graph Algorithms with Predictions
Joan Boyar, Faith Ellen, Kim S. Larsen
We initiate the study of deterministic distributed graph algorithms with predictions in synchronous message passing systems. The process at each node in the graph is given a predic…
Complexity Classes for Online Problems with and without Predictions
Magnus Berg, Joan Boyar, Lene M. Favrholdt +1
With the developments in machine learning, there has been a surge in interest and results focused on algorithms utilizing predictions, not least in online algorithms where most new…
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…
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…
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…
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…
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…
Constructive Relationships Between Algebraic Thickness and Normality
Joan Boyar, Magnus Gausdal Find
We study the relationship between two measures of Boolean functions; \emph{algebraic thickness} and \emph{normality}. For a function , the algebraic thickness is a variant of th…
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…
Multiplicative Complexity of Vector Valued Boolean Functions
Magnus Gausdal Find, Joan Boyar
We consider the multiplicative complexity of Boolean functions with multiple bits of output, studying how large a multiplicative complexity is necessary and sufficient to provide a…
Tight Bounds for Restricted Grid Scheduling
Joan Boyar, Faith Ellen
The following online bin packing problem is considered: Items with integer sizes are given and variable sized bins arrive online. A bin must be used if there is still an item remai…
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…