收录:
摘要:
Recently intensive interest has been raised 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 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. © 2014, Operations Research Society of China, Periodicals Agency of Shanghai University, and Springer-Verlag Berlin Heidelberg.
关键词:
通讯作者信息:
电子邮件地址:
来源 :
Journal of the Operations Research Society of China
ISSN: 2194-668X
年份: 2014
期: 3
卷: 2
页码: 271-290
归属院系: