matroids

• Faster Submodular Maximization for Several Classes of Matroids

  ICALP 2023

  Monika Henzinger, Paul Liu, Jan Vondrak, Da Wei Zheng

  ---

  In this work, we develop algorithms for monotone submodular maximization constrained by graphic, transversal matroids, or laminar matroids in time near-linear in the size of their representation. Our algorithms achieve an optimal approximation of 1−1/e−ϵ and both generalize and accelerate the results of Ene and Nguyen [ICALP '19]. In fact, the running time of our algorithm cannot be improved within the fast continuous greedy framework of Badanidiyuru and Vondrák [SODA '14].

  submodular optimization data structures matroids

  [pdf]