Bi-Weekly Talk: Eran Rosenbluth: The Solidarity Cover Problem

Mittwoch, 27.10.2021, 10.30 Uhr

Ort: Online Session

Vortragender: Eran Rosenbluth



Survey of a work-in-progress. Motivated initially by real world scenarios in the domains of sensing and communication, we define a geometric covering problem which we name Solidarity Cover. We then make a connection between that problem and an already-studied graph problem named Domatic Number (DNP). Using known results for the DNP and the close relation between the two problems we draw hardness results and approximation bounds for several settings of the new problem. We describe a 3-approximation algorithm to one of the problem's variants and conclude with questions still open (to the best of our knowledge).