5 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…
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…