.png){kind=icon}
返回
Improved approximation algorithms for k-submodular maximization under a knapsack constraint
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2023.106452.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
我们研究了在大小的地面集上背包约束下的k-子模最大化问题。这个问题在各个领域都有许多应用，例如多主题传播，多传感器放置，合作游戏等。然而，随着实际应用中实例规模的增加，针对所研究问题的现有算法在实践中面临挑战。本文针对该问题介绍了三种确定性和逼近算法，这些算法显着提高了现有实用算法的逼近率和查询复杂度。我们的第一个算法FA在O(nk) 查询复杂度内返回1/10的近似比率。第二个，IFA，提高了O(nk/epsilon) 查询中1/4-epsilon的近似比。最后一个IFA将近似比升级为O(nk log(1/epsilon) 查询复杂度中的1/3-epsilon，其中 ..是一个精度参数。我们的算法是第一个仅在O(nk) 查询复杂度内提供恒定近似比的算法，实现结果的新颖思想在于两个组件。首先，我们将地面集分为两个适当的子集，以找到具有O(nk) 查询的这些子集的近似最优解。其次，我们设计了算法框架，将第一种算法的解与贪婪阈值法相结合，以提高解的质量。除了理论分析外，我们还在某些情况下通过一些实验评估了我们提出的建议: 影响最大化，信息覆盖最大化和问题的传感器放置。结果证实，我们的算法作为尖端技术 (包括流和非流算法) 确保了理论质量，并且还显着减少了查询数量。
Keyword:
Combinatorial optimization
Approximation algorithm
k-submodular
Knapsack constraint
期刊
C
IF:
4.3
论文数:
6.5K
被引数:
1.8W
机构
引用论文
Constrained Monotone k-Submodular Function Maximization Using Multiobjective Evolutionary Algorithms With Theoretical Guarantee使用具有理论保证的多目标进化算法的约束单调k-子模函数最大化
.png){kind=icon}
PREAI
分享收藏
A mobile multi-agent sensing problem with submodular functions under a partition matroid分区拟阵下具有子模功能的移动多智能体感知问题
PREAI
分享收藏
查看更多内容