Regularized Submodular Maximization over Integer Lattice
摘要
In this paper, we delve deeply into the problem of regularized submodular maximization over the integer lattice. Our objective function, \(f-c\) , is simply the difference between a non-negative monotone submodular function f and a non-negative modular function c. While this problem has gained much attention in the set scenario recently, we broaden our focus to include the integer lattice. Our main contribution is an efficient algorithm for this problem, backed by strong approximation guarantees. We also test our algorithm in the real-world application of D-optimal design. To ensure fair comparisons, we created a greedy algorithm and calculated its approximation guarantees. The results show that our algorithm performs remarkably well with real datasets.