Zobrazeno 1 - 3
of 3
pro vyhledávání: '"Picavet, Timothé"'
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 in a $2$-colored tree in which white nodes of degree $d$ and black node
Externí odkaz:
http://arxiv.org/abs/2312.12243
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 is to pack as many of these rectangles inside the box without overlap
Externí odkaz:
http://arxiv.org/abs/2307.10672
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 a locally checkable labeling problem (LCL) can be derandomized with at
Externí odkaz:
http://arxiv.org/abs/2305.07351