4 papers
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…
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…