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

Wednesday, October 27, 2021, 10:30am

Location: Online session

Speaker: Eran Rosenbluth

 

Abstract: 

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).