Approximations for Monotone and Nonmonotone Submodular Maximization with Knapsack Constraints

• 成果类型: Article
• 署名作者: Kulik, Ariel; Shachnai, Hadas; Tamir, Tami
• 署名单位: Technion Israel Institute of Technology; Reichman University
• 刊物名称: MATHEMATICS OF OPERATIONS RESEARCH
• ISSN/ISSBN: 0364-765X
• DOI: 10.1287/moor.2013.0592
• 发表日期: 2013
• 页码: 729-739
• 关键词: set function subject

摘要

Submodular maximization generalizes many fundamental problems in discrete optimization, including Max-Cut in directed/undirected graphs, maximum coverage, maximum facility location, and marketing over social networks. In this paper we consider the problem of maximizing any submodular function subject to d knapsack constraints, where d is a fixed constant. We establish a strong relation between the discrete problem and its continuous relaxation, obtained through extension by expectation of the submodular function. Formally, we show that, for any nonnegative submodular function, an alpha-approximation algorithm for the continuous relaxation implies a randomized (alpha - epsilon)-approximation algorithm for the discrete problem. We use this relation to obtain an (e(-1) - epsilon)-approximation for the problem, and a nearly optimal (1 - e(-1) - epsilon)-approximation ratio for the monotone case, for any epsilon > 0. We further show that the probabilistic domain defined by a continuous solution can be reduced to yield a polynomial-size domain, given an oracle for the extension by expectation. This leads to a deterministic version of our technique.