September 10 | 13:00 | Building 8, room 424

---

 

We define the fractional dominating set problem as follows: Given is a directed graph, with a value and cost associated with each node and a weight between 0 and 1 associated with each edge (u, v). The weight of an edge (u, v) represents the fraction of the value of v covered by u.  The objective is to select the set of nodes under some budget constraint that maximizes the total coverage of all nodes in the graph. 

 

This problem is closely related to budgeted dominating set.  A result by Khuller, et al. shows that this cannot be approximated by a factor greater than (e-1)/e, unless P=NP, and that modified greedy selection guarantees this factor.  Sviridenko extended these results to all submodular functions of node coverage by a set of nodes. 

 

The question we try to answer is what happens when the selection is optimized according to one coverage function but evaluated by another, both being submodular?  How much worse is the coverage than if selection was made according to the right criteria?  In my talk, I will discuss some of our results in this area and how they apply to sensor networks.  In sensor networks, one would like to use a limited set of sensors to predict the values of all other sensors to conserve resources.

 

 

Simon Shamoun received his Ph.D. in computer science from the CUNY Graduate Center in 2011 and continues to work with his thesis advisor in this area.  He most recently worked as a post-doctorate fellow at Bar Ilan University on search problems in mobile ad hoc networks, and then at Ben Gurion University on formal specifications for robotic systems.