Submodularity

From Cohen Courses
Jump to navigationJump to search

This is a technical method discussed in Social Media Analysis 10-802 in Spring 2010.

Submodularity is a property of cost functions that explains the utility of greedy methods and is able to speed up performance when used on cost functions that have this trait.

For the sets and an additional element that is not . A cost (or reward) function on these sets is said to be sumbodular if

Submodularity can be thought of as diminishing returns. In the sensor placement problem, this can be thought of as getting less bang for your buck. As you continue to add senors the network, each new sensor is more likely to overlap in coverage with existing ones. Because of this, greedy methods that place sensors according minimizing cost at every step perform relatively well.


Related Papers