The problem of maximizing a submodular set function is one of the fundamental combinatorial optimization problems. Here, we consider the problem of maximizing a DR-submodular function on distributive lattice. This problem has applications in order-constrained of sensor activation problem, and order-constrained document summarization problem. In the set case, the most succeeded approach is the continuous relaxation. Thus, we want to extend the methodology to the distributive lattice case.

The contribution of this study is a continuous greedy-type algorithm for a multiple knapsack-constrained DR-submodular maximization problem on a distributive lattice. We introduce a new geometric object, called the median complex, and exploit its structure for "straight lines". This structure leads the continuous greedy algorithm on the distributive lattice.

This is the joint work with Soh Nakashima (The University of Tokyo) and Yutaro Yamaguchi (Osaka University)