论文标题
通过贪婪算法和多代理执行中有限信息的影响，非管道最大化
Non-Submodular Maximization via the Greedy Algorithm and the Effects of Limited Information in Multi-Agent Execution
论文作者
论文摘要
我们在寻求最大化归一化的单调，但不一定是简单分区的矩阵约束下的归一化，单调目标函数方面，在贪婪算法的最坏情况下提供理论界限。如果在每个计划步骤中可获得有限的信息，我们还为贪婪算法的性能提供了最坏的情况。由于在贪婪算法的分布式执行过程中，由于不可靠的通信，我们特别考虑了有限的信息。我们利用曲率的概念来实现归一化的单调集函数来开发本工作中提供的界限。为了证明这项工作中提供的界限的价值，我们使用自主水下车辆收集的现实世界数据分析了搜索目标功能的好处，并显示了尽管目标函数不显性，但仍可以实现理论上的近似保证。
We provide theoretical bounds on the worst case performance of the greedy algorithm in seeking to maximize a normalized, monotone, but not necessarily submodular objective function under a simple partition matroid constraint. We also provide worst case bounds on the performance of the greedy algorithm in the case that limited information is available at each planning step. We specifically consider limited information as a result of unreliable communications during distributed execution of the greedy algorithm. We utilize notions of curvature for normalized, monotone set functions to develop the bounds provided in this work. To demonstrate the value of the bounds provided in this work, we analyze a variant of the benefit of search objective function and show, using real-world data collected by an autonomous underwater vehicle, that theoretical approximation guarantees are achieved despite non-submodularity of the objective function.
