Maximizing monotone submodular functions over the integer lattice

• 成果类型: Article
• 署名作者: Soma, Tasuku; Yoshida, Yuichi
• 署名单位: University of Tokyo; Research Organization of Information & Systems (ROIS); National Institute of Informatics (NII) - Japan
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-018-1324-y
• 发表日期: 2018
• 页码: 539-563
• 关键词: function maximization; function subject; constraint

摘要

The problem of maximizing non-negative monotone submodular functions under a certain constraint has been intensively studied in the last decade. In this paper, we address the problem for functions defined over the integer lattice. Suppose that a nonnegative monotone submodular function f : Zn +. R+ is given via an evaluation oracle. Assume further that f satisfies the diminishing return property, which is not an immediate consequence of submodularity when the domain is the integer lattice. Given this, we design polynomial-time (1 -1/ e -)-approximation algorithms for a cardinality constraint, a polymatroid constraint, and a knapsack constraint. For a cardinality constraint, we also provide a (1-1/ e -)-approximation algorithm with slightly worse time complexity that does not rely on the diminishing return property.