Recently there has been intensive interest on approximation of the NP-hard submodular maximization problem due to their theoretical and practical significance. In this work, we extend this line of research by focusing on the simultaneous approximation of multiple submodular function maximization. We address existence and nonexistence results for both deterministic and randomized approximation when the submodular functions are symmetric and asymmetric, respectively, along with algorithmic corollaries. We offer complete characterization of the symmetric case and partial results on the asymmetric case.
Citation
Working Paper Series 2012-005, University of New Brunswick, Canada
Article
View Simultaneous approximation of multi-criteria submodular function maximization