5 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…
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…
Time Fairness in Online Knapsack Problems
Adam Lechowicz, Rik Sengupta, Bo Sun +2
The online knapsack problem is a classic problem in the field of online algorithms. Its canonical version asks how to pack items of different values and weights arriving online int…
Online Bin Packing with Predictions
Spyros Angelopoulos, Shahin Kamali, Kimia Shadkami
Bin packing is a classic optimization problem with a wide range of applications, from load balancing to supply chain management. In this work, we study the online variant of the pr…
Online Computation with Untrusted Advice
Spyros Angelopoulos, Christoph Dürr, Shendan Jin +2
We study a generalization of the advice complexity model of online computation in which the advice is provided by an untrusted source. Our objective is to quantify the impact of un…