2021/05/11 by Micah Corah, Corah, Micah
Computer Science · #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #FOS: Electrical engineering #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Search Problems #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2105.04793
openalex publication_date 2021/05/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Resilient submodular maximization refers to the combinatorial problems studied by Nemhauser and Fisher and asks how to maximize an objective given a number of adversarial removals. For example, one application of this problem is multi-robot sensor planning with adversarial attacks. However, more general applications of submodular maximization are also relevant. Tzoumas et al. obtain near-optimal solutions to this problem by taking advantage of a property called curvature to produce a mechanism which makes certain bait elements interchangeable with other elements of the solution that are produced via typical greedy means. This document demonstrates that -- at least in theory -- applying the method for selection of bait elements to the entire solution can improve that guarantee on solution quality.