Multiple knapsack-constrained monotone DR-submodular maximization on distributive lattice - Continuous Greedy Algorithm on Median Complex

• 成果类型: Article
• 署名作者: Maehara, Takanori; Nakashima, So; Yamaguchi, Yutaro
• 署名单位: RIKEN; University of Tokyo; Kyushu University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-021-01620-7
• 发表日期: 2022
• 页码: 85-119
• 关键词: probability-inequalities; function subject; matroids

摘要

We consider a problem of maximizing a monotone DR-submodular function under multiple order-consistent knapsack constraints on a distributive lattice. Because a distributive lattice is used to represent a dependency constraint, the problem can represent a dependency constrained version of a submodular maximization problem on a set. We propose a (1-1/e)-approximation algorithm for this problem. To achieve this result, we generalize the continuous greedy algorithm to distributive lattices: We choose a median complex as a continuous relaxation of the distributive lattice and define the multilinear extension on it. We show that the median complex admits special curves, named uniform linear motions. The multilinear extension of a DR-submodular function is concave along a positive uniform linear motion, which is a key property used in the continuous greedy algorithm.