TY - JOUR

T1 - Multiple knapsack-constrained monotone DR-submodular maximization on distributive lattice

T2 - — Continuous Greedy Algorithm on Median Complex —

AU - Maehara, Takanori

AU - Nakashima, So

AU - Yamaguchi, Yutaro

N1 - Publisher Copyright:
© 2021, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society.

PY - 2022/7

Y1 - 2022/7

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85100498752&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85100498752&partnerID=8YFLogxK

U2 - 10.1007/s10107-021-01620-7

DO - 10.1007/s10107-021-01620-7

M3 - Article

AN - SCOPUS:85100498752

SN - 0025-5610

VL - 194

SP - 85

EP - 119

JO - Mathematical Programming

JF - Mathematical Programming

IS - 1-2

ER -