In recent years, the k-submodular maximization problem has garnered significant attention. However, many practical applications cannot be strictly modeled as k-submodular maximization problems. This highlights the necessity of studying the maximization of approximately non-k-submodular. In this paper, we are committed to solving the problem of maximizing \(\epsilon \) -approximately \(\alpha \) -weakly diminishing returns functions under p-system and \(\ell \) knapsack constraints. We first give a greedy algorithm, achieving a \(\frac{1}{(1+\epsilon ')(1+\frac{1+\epsilon }{\alpha ^2(1-\epsilon )}p+\frac{2(1+\epsilon )^2}{\alpha ^2(1-\epsilon )^2}\ell )}\) - approximation with the \(O(n^2(1+k)\log (2n))\) time complexity, where \(\epsilon '\) is a very small positive number. Then we further introduce an improved algorithm that not only enhances the approximation ratio to \( \frac{\min \{1,\frac{1}{\alpha (1+\epsilon ')}\}}{1+\frac{1+\epsilon }{\alpha ^2(1-\epsilon )}[(1+\epsilon ')(p+\alpha \epsilon ')+\frac{7}{4}\ell ]}\) , but also reduces the time complexity to \(O(nk\log \frac{n}{\epsilon '}\log (2n))\) .

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

Approximately Non-k-submodular Maximization Under p-System and \(\ell \) Knapsack Constraints \(^\star \)

  • Hanlu Ye,
  • Heqing Li,
  • Min Li,
  • Yang Zhou,
  • Qian Liu

摘要

In recent years, the k-submodular maximization problem has garnered significant attention. However, many practical applications cannot be strictly modeled as k-submodular maximization problems. This highlights the necessity of studying the maximization of approximately non-k-submodular. In this paper, we are committed to solving the problem of maximizing \(\epsilon \) -approximately \(\alpha \) -weakly diminishing returns functions under p-system and \(\ell \) knapsack constraints. We first give a greedy algorithm, achieving a \(\frac{1}{(1+\epsilon ')(1+\frac{1+\epsilon }{\alpha ^2(1-\epsilon )}p+\frac{2(1+\epsilon )^2}{\alpha ^2(1-\epsilon )^2}\ell )}\) - approximation with the \(O(n^2(1+k)\log (2n))\) time complexity, where \(\epsilon '\) is a very small positive number. Then we further introduce an improved algorithm that not only enhances the approximation ratio to \( \frac{\min \{1,\frac{1}{\alpha (1+\epsilon ')}\}}{1+\frac{1+\epsilon }{\alpha ^2(1-\epsilon )}[(1+\epsilon ')(p+\alpha \epsilon ')+\frac{7}{4}\ell ]}\) , but also reduces the time complexity to \(O(nk\log \frac{n}{\epsilon '}\log (2n))\) .