Bi-Weekly Talk: Eran Rosenbluth: The Solidarity Cover Problem
Wednesday, October 27, 2021, 10:30am
Location: Online session
Speaker: 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).