Non-Submodular Maximization via the Greedy Algorithm and the Effects of Limited Information in Multi-Agent Execution
Benjamin Biggs,James McMahon,Philip Baldoni,Daniel J. Stilwell,Benjamin Biggs,James McMahon,Philip Baldoni,Daniel J. Stilwell
We provide theoretical bounds on the worst case performance of the greedy algorithm in seeking to maximize a normalized, monotone, but not necessarily submodular ob-jective 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 conside...
