---
res:
  bibo_abstract:
  - "The maximization of submodular functions have found widespread application in
    areas such as machine learning, combinatorial optimization, and economics, where
    practitioners often wish to enforce various constraints; the matroid constraint
    has been investigated extensively due to its algorithmic properties and expressive
    power. Though tight approximation algorithms for general matroid constraints exist
    in theory, the running times of such algorithms typically scale quadratically,
    and are not practical for truly large scale settings. Recent progress has focused
    on fast algorithms for important classes of matroids given in explicit form. Currently,
    nearly-linear time algorithms only exist for graphic and partition matroids [Alina
    Ene and Huy L. Nguyen, 2019]. 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 [Alina Ene and Huy L. Nguyen, 2019]. In fact, the
    running time of our algorithm cannot be improved within the fast continuous greedy
    framework of Badanidiyuru and Vondrák [Ashwinkumar Badanidiyuru and Jan Vondrák,
    2014].\r\nTo achieve near-linear running time, we make use of dynamic data structures
    that maintain bases with approximate maximum cardinality and weight under certain
    element updates. These data structures need to support a weight decrease operation
    and a novel Freeze operation that allows the algorithm to freeze elements (i.e.
    force to be contained) in its basis regardless of future data structure operations.
    For the laminar matroid, we present a new dynamic data structure using the top
    tree interface of Alstrup, Holm, de Lichtenberg, and Thorup [Stephen Alstrup et
    al., 2005] that maintains the maximum weight basis under insertions and deletions
    of elements in O(log n) time. This data structure needs to support certain subtree
    query and path update operations that are performed every insertion and deletion
    that are non-trivial to handle in conjunction. For the transversal matroid the
    Freeze operation corresponds to requiring the data structure to keep a certain
    set S of vertices matched, a property that we call S-stability. While there is
    a large body of work on dynamic matching algorithms, none are S-stable and maintain
    an approximate maximum weight matching under vertex updates. We give the first
    such algorithm for bipartite graphs with total running time linear (up to log
    factors) in the number of edges.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Monika H
      foaf_name: Henzinger, Monika H
      foaf_surname: Henzinger
      foaf_workInfoHomepage: http://www.librecat.org/personId=540c9bbd-f2de-11ec-812d-d04a5be85630
    orcid: 0000-0002-5008-6530
  - foaf_Person:
      foaf_givenName: Paul
      foaf_name: Liu, Paul
      foaf_surname: Liu
  - foaf_Person:
      foaf_givenName: Jan
      foaf_name: Vondrák, Jan
      foaf_surname: Vondrák
  - foaf_Person:
      foaf_givenName: Da Wei
      foaf_name: Zheng, Da Wei
      foaf_surname: Zheng
  bibo_doi: 10.4230/LIPIcs.ICALP.2023.74
  bibo_volume: 261
  dct_date: 2023^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/1868-8969
  - http://id.crossref.org/issn/9783959772785
  dct_language: eng
  dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
  dct_title: Faster submodular maximization for several classes of matroids@
...