Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
Tight Competitive Bounds for Online Matching on Forests
Bartłomiej Bosek, Grzegorz Gutowski, Paweł Putra +1
We study the online matching problem, its fractional relaxation, and the fractional online vertex cover problem on forests whose edges arrive one at a time in an arbitrary order. M…
cs.DS2026
Online and Incremental Fractional Vertex Cover on Trees
Júlia Baligács, Bartłomiej Bosek, Yann Disser +5
In this paper we study the fractional vertex cover problem on trees in two related models: online and incremental. In the online model, the vertices of the tree are known a priori…
cs.DS2026
A tight lower bound for malicious online bipartite matching with limited recourse budget
Julia Baligacs, Bartłomiej Bosek, Paweł Putra +2
We study one-sided online bipartite matching with recourse. In this setting, one side of a bipartite graph is known in advance, while vertices on the other side arrive online toget…