On Bisubmodular Maximization


Ajit Singh, Andrew Guillory, Jeff Bilmes ;
Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, PMLR 22:1055-1063, 2012.


Bisubmodularity extends the concept of submodularity to set functions with two arguments. We show how bisubmodular maximization leads to richer value-of-information problems, using examples in sensor placement and feature selection. We present the first constant-factor approximation algorithm for a wide class of bisubmodular maximizations.

Related Material