Maximizing Monotone Submodular Functions over the Integer Lattice

被引:13
作者
Soma, Tasuku [1 ]
Yoshida, Yuichi [2 ]
机构
[1] Univ Tokyo, Grad Sch Informat Sci & Technol, Tokyo, Japan
[2] Natl Inst Informat & Preferred Infrastruct Inc, Tokyo, Japan
来源
INTEGER PROGRAMMING AND COMBINATORIAL OPTIMIZATION, IPCO 2016 | 2016年 / 9682卷
关键词
FUNCTION SUBJECT;
D O I
10.1007/978-3-319-33461-5_27
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
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 non-negative monotone submodular function f : Z(+)(n) -> R+ is given via an evaluation oracle. Assume further that f satisfies the diminishing return property, which is not an immediate consequence of the submodularity when the domain is the integer lattice. Then, we show polynomial-time (1 - 1/e - epsilon)-approximation algorithm for cardinality constraints, polymatroid constraints, and knapsack constraints. For a cardinality constraint, we also show a (1 - 1/e - epsilon)-approximation algorithm with slightly worse time complexity that does not rely on the diminishing return property. Our algorithms for a polymatroid constraint and a knapsack constraint first extend the domain of the objective function to the Euclidean space and then run the continuous greedy algorithm. We give two different kinds of continuous extensions, one is for polymatroid constraints and the other is for knapsack constraints, which might be of independent interest.
引用
收藏
页码:325 / 336
页数:12
相关论文
共 28 条
[1]  
Alon N., 2012, P 21 INT C WORLD WID, P381
[2]  
[Anonymous], 2003, PROC 9 KDD
[3]  
Badanidiyuru A, 2014, 25 ACM SIAM S DISCR, P1497
[4]   A Tight Linear Time (1/2)-Approximation for Unconstrained Submodular Maximization [J].
Buchbinder, Niv ;
Feldman, Moran ;
Naor, Joseph ;
Schwartz, Roy .
2012 IEEE 53RD ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2012, :649-658
[5]  
Buchbinder Niv, 2014, P 25 ANN ACM SIAM S, P1433, DOI [10.1137/1.9781611973402.106, DOI 10.1137/1.9781611973402.106]
[6]  
Buchbinder Niv., 2016, Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, P392
[7]   MAXIMIZING A MONOTONE SUBMODULAR FUNCTION SUBJECT TO A MATROID CONSTRAINT [J].
Calinescu, Gruia ;
Chekuri, Chandra ;
Pal, Martin ;
Vondrak, Jan .
SIAM JOURNAL ON COMPUTING, 2011, 40 (06) :1740-1766
[8]   Dependent Randomized Rounding via Exchange Properties of Combinatorial Structures [J].
Chekuri, Chandra ;
Vondrak, Jan ;
Zenklusen, Rico .
2010 IEEE 51ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 2010, :575-584
[9]   TESTING MEMBERSHIP IN MATROID POLYHEDRA [J].
CUNNINGHAM, WH .
JOURNAL OF COMBINATORIAL THEORY SERIES B, 1984, 36 (02) :161-188
[10]   How to Influence People with Partial Incentives [J].
Demaine, Erik D. ;
Hajiaghayi, MohammadTaghi ;
Mahini, Hamid ;
Malec, David L. ;
Raghavan, S. ;
Sawant, Anshul ;
Zadimoghadam, Morteza .
WWW'14: PROCEEDINGS OF THE 23RD INTERNATIONAL CONFERENCE ON WORLD WIDE WEB, 2014, :937-947