1 citations · 1 across the 6 of their papers we have counts for
3 papers · 1 filter
Distributed Binary Labeling Problems in High-Degree Graphs
Henrik Lievonen, Timothé Picavet, Jukka Suomela
Balliu et al. (DISC 2020) classified the hardness of solving binary labeling problems with distributed graph algorithms; in these problems the task is to select a subset of edges i…
A parameterized approximation scheme for the 2D-Knapsack problem with wide items
Michal Pilipczuk, Mathieu Mari, Timothe Picavet
We study a natural geometric variant of the classic Knapsack problem called 2D-Knapsack: we are given a set of axis-parallel rectangles and a rectangular bounding box, and the goal…
Distributed derandomization revisited
Sameep Dahal, Francesco d'Amore, Henrik Lievonen +2
One of the cornerstones of the distributed complexity theory is the derandomization result by Chang, Kopelowitz, and Pettie [FOCS 2016]: any randomized LOCAL algorithm that solves…