2 papers
cs.DS2024
On the Advice Complexity of Online Matching on the Line
Béla Csaba, Judit Nagy-György
We consider the matching problem on the line with advice complexity. We give a 1-competitive online algorithm with advice complexity and show that there is no 1-competitive…
cs.DS2023
On the Advice Complexity of Online Unit Clustering
Judit Nagy-György
In online unit clustering, points of a metric space arriving one by one must be partitioned into clusters of diameter at most 1, where the cost is the number of clusters. This pape…