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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Regularized Submodular Maximization over Integer Lattice

  • Zhicheng Liu,
  • Yang Lv,
  • Yapu Zhang,
  • Zhenning Zhang

摘要

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.