---
_id: '14086'
abstract:
- lang: eng
  text: "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."
acknowledgement: " Monika Henzinger: This project has received funding from the European
  Research Council\r\n(ERC) under the European Union’s Horizon 2020 research and innovation
  programme (Grant\r\nagreement No. 101019564 “The Design of Modern Fully Dynamic
  Data Structures (MoDynStruct)” and from the Austrian Science Fund (FWF) project
  “Static and Dynamic Hierarchical Graph Decompositions”, I 5982-N, and project “Fast
  Algorithms for a Reactive Network Layer (ReactNet)”, P 33775-N, with additional
  funding from the netidee SCIENCE Stiftung, 2020–2024. Jan Vondrák: Supported by
  NSF Award 2127781."
alternative_title:
- LIPIcs
article_number: '74'
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
- first_name: Paul
  full_name: Liu, Paul
  last_name: Liu
- first_name: Jan
  full_name: Vondrák, Jan
  last_name: Vondrák
- first_name: Da Wei
  full_name: Zheng, Da Wei
  last_name: Zheng
citation:
  ama: 'Henzinger M, Liu P, Vondrák J, Zheng DW. Faster submodular maximization for
    several classes of matroids. In: <i>50th International Colloquium on Automata,
    Languages, and Programming</i>. Vol 261. Schloss Dagstuhl - Leibniz-Zentrum für
    Informatik; 2023. doi:<a href="https://doi.org/10.4230/LIPIcs.ICALP.2023.74">10.4230/LIPIcs.ICALP.2023.74</a>'
  apa: 'Henzinger, M., Liu, P., Vondrák, J., &#38; Zheng, D. W. (2023). Faster submodular
    maximization for several classes of matroids. In <i>50th International Colloquium
    on Automata, Languages, and Programming</i> (Vol. 261). Paderborn, Germany: Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik. <a href="https://doi.org/10.4230/LIPIcs.ICALP.2023.74">https://doi.org/10.4230/LIPIcs.ICALP.2023.74</a>'
  chicago: Henzinger, Monika, Paul Liu, Jan Vondrák, and Da Wei Zheng. “Faster Submodular
    Maximization for Several Classes of Matroids.” In <i>50th International Colloquium
    on Automata, Languages, and Programming</i>, Vol. 261. Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2023. <a href="https://doi.org/10.4230/LIPIcs.ICALP.2023.74">https://doi.org/10.4230/LIPIcs.ICALP.2023.74</a>.
  ieee: M. Henzinger, P. Liu, J. Vondrák, and D. W. Zheng, “Faster submodular maximization
    for several classes of matroids,” in <i>50th International Colloquium on Automata,
    Languages, and Programming</i>, Paderborn, Germany, 2023, vol. 261.
  ista: 'Henzinger M, Liu P, Vondrák J, Zheng DW. 2023. Faster submodular maximization
    for several classes of matroids. 50th International Colloquium on Automata, Languages,
    and Programming. ICALP: Automata, Languages and Programming, LIPIcs, vol. 261,
    74.'
  mla: Henzinger, Monika, et al. “Faster Submodular Maximization for Several Classes
    of Matroids.” <i>50th International Colloquium on Automata, Languages, and Programming</i>,
    vol. 261, 74, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a
    href="https://doi.org/10.4230/LIPIcs.ICALP.2023.74">10.4230/LIPIcs.ICALP.2023.74</a>.
  short: M. Henzinger, P. Liu, J. Vondrák, D.W. Zheng, in:, 50th International Colloquium
    on Automata, Languages, and Programming, Schloss Dagstuhl - Leibniz-Zentrum für
    Informatik, 2023.
conference:
  end_date: 2023-07-14
  location: Paderborn, Germany
  name: 'ICALP: Automata, Languages and Programming'
  start_date: 2023-07-10
corr_author: '1'
date_created: 2023-08-20T22:01:14Z
date_published: 2023-07-01T00:00:00Z
date_updated: 2025-07-10T11:50:45Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.ICALP.2023.74
ec_funded: 1
external_id:
  arxiv:
  - '2305.00122'
file:
- access_level: open_access
  checksum: a5eef225014e003efbfbe4830fdd23cb
  content_type: application/pdf
  creator: dernst
  date_created: 2023-08-21T07:04:36Z
  date_updated: 2023-08-21T07:04:36Z
  file_id: '14090'
  file_name: 2023_LIPIcsICALP_HenzingerM.pdf
  file_size: 930943
  relation: main_file
  success: 1
file_date_updated: 2023-08-21T07:04:36Z
has_accepted_license: '1'
intvolume: '       261'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
  call_identifier: H2020
  grant_number: '101019564'
  name: The design and evaluation of modern fully dynamic data structures
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
  grant_number: I05982
  name: Static and Dynamic Hierarchical Graph Decompositions
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
  grant_number: P33775
  name: Fast Algorithms for a Reactive Network Layer
publication: 50th International Colloquium on Automata, Languages, and Programming
publication_identifier:
  isbn:
  - '9783959772785'
  issn:
  - 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Faster submodular maximization for several classes of matroids
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 261
year: '2023'
...