21 citations · 39 across the 20 of their papers we have counts for
7 papers · 1 filter
A rainbow partition theorem for trees and connected maximin share allocations of chores
Marcin Anholcer, Maciej Bartkowiak, Bartłomiej Bosek +3
Xiao, Qiu, and Huang (AAMAS 2023) and independently Lonc (personal communication) asked whether indivisible chores located at the vertices of a tree can always be allocated to …
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…
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…
Arboricity Nearly Bounds Degeneracy
Michał Lasoń, Bartłomiej Bosek, Grzegorz Gutowski +1
Arboricity and degeneracy are two fundamental and closely related graph parameters that measure the sparsity of a graph. Every -degenerate graph is -arboric, but some -arb…
Dynamic domination and independence in sparse graphs
Bartłomiej Bosek, Wojciech Nadara, Michał Pilipczuk +1
Let be a class of graphs of bounded expansion and be fixed. We give a dynamic data structure that for a given dynamic graph , updated by edge i…
Epistemic fair division of independence structures
Marcin Anholcer, Maciej Bartkowiak, Bartłomiej Bosek +1
We study the problem of fair division of indivisible goods with constraints imposed by a prescribed independence structure, that is, a family of subsets of goods closed under takin…
Dynamic data structures for twin-ordered matrices
Bartłomiej Bosek, Jadwiga Czyżewska, Evangelos Kipouridis +4
We present a dynamic data structure for representing binary matrices that are -twin-ordered, for a~fixed parameter . Our structure supports cell queries and singl…