2024/05/31 by Eric Balkanski, Balkanski, Eric, Steven DiSilvio +4
Computer Science · #Advanced Algebra and Logic #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2406.00148
openalex publication_date 2024/05/31 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this work, we study the classical problem of maximizing a submodular function subject to a matroid constraint. We develop deterministic algorithms that are very parsimonious with respect to querying the submodular function, for both the case when the submodular function is monotone and the general submodular case. In particular, we present a 1/4 approximation algorithm for the monotone case that uses exactly one query per element, which gives the same total number of queries n as the number of queries required to compute the maximum singleton. For the general case, we present a constant factor approximation algorithm that requires 2 queries per element, which is the first algorithm for this problem with linear query complexity in the size of the ground set.