8 citations · 9 across the 12 of their papers we have counts for
16 papers
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…
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…
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…
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…
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…
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…
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…
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…