Abstract:

Recently intensive interest has been raised on approximation of the NPhard
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
the 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.

Key words: Multi-criteria ,  Submodular function maximization ,  Approximation
algorithm , Existence