---
_id: '13236'
abstract:
- lang: eng
  text: We present an auction algorithm using multiplicative instead of constant weight
    updates to compute a (1−ε)-approximate maximum weight matching (MWM) in a bipartite
    graph with n vertices and m edges in time O(mε−1log(ε−1)), matching the running
    time of the linear-time approximation algorithm of Duan and Pettie [JACM ’14].
    Our algorithm is very simple and it can be extended to give a dynamic data structure
    that maintains a (1−ε)-approximate maximum weight matching under (1) one-sided
    vertex deletions (with incident edges) and (2) one-sided vertex insertions (with
    incident edges sorted by weight) to the other side. The total time time used is
    O(mε−1log(ε−1)), where m is the sum of the number of initially existing and inserted
    edges.
acknowledgement: The first author thanks to Chandra Chekuri for useful discussions
  about this paper. This project has received funding from the European Research Council
  (ERC) under the European Union’s Horizon 2020 research and innovation programme
  (Grant agreement No. 101019564 “The Design of Modern Fully Dynamic Data Structures
  (MoDynStruct)” and from the Austrian Science Fund (FWF) project “Fast Algorithms
  for a Reactive Network Layer (ReactNet)”, P 33775-N, with additional funding from
  the netidee SCIENCE Stiftung, 2020–2024.
alternative_title:
- LNCS
article_processing_charge: No
arxiv: 1
author:
- first_name: Da Wei
  full_name: Zheng, Da Wei
  last_name: Zheng
- first_name: Monika H
  full_name: Henzinger, Monika H
  id: 540c9bbd-f2de-11ec-812d-d04a5be85630
  last_name: Henzinger
  orcid: 0000-0002-5008-6530
citation:
  ama: 'Zheng DW, Henzinger MH. Multiplicative auction algorithm for approximate maximum
    weight bipartite matching. In: <i>International Conference on Integer Programming
    and Combinatorial Optimization</i>. Vol 13904. Springer Nature; 2023:453-465.
    doi:<a href="https://doi.org/10.1007/978-3-031-32726-1_32">10.1007/978-3-031-32726-1_32</a>'
  apa: 'Zheng, D. W., &#38; Henzinger, M. H. (2023). Multiplicative auction algorithm
    for approximate maximum weight bipartite matching. In <i>International Conference
    on Integer Programming and Combinatorial Optimization</i> (Vol. 13904, pp. 453–465).
    Madison, WI, United States: Springer Nature. <a href="https://doi.org/10.1007/978-3-031-32726-1_32">https://doi.org/10.1007/978-3-031-32726-1_32</a>'
  chicago: Zheng, Da Wei, and Monika H Henzinger. “Multiplicative Auction Algorithm
    for Approximate Maximum Weight Bipartite Matching.” In <i>International Conference
    on Integer Programming and Combinatorial Optimization</i>, 13904:453–65. Springer
    Nature, 2023. <a href="https://doi.org/10.1007/978-3-031-32726-1_32">https://doi.org/10.1007/978-3-031-32726-1_32</a>.
  ieee: D. W. Zheng and M. H. Henzinger, “Multiplicative auction algorithm for approximate
    maximum weight bipartite matching,” in <i>International Conference on Integer
    Programming and Combinatorial Optimization</i>, Madison, WI, United States, 2023,
    vol. 13904, pp. 453–465.
  ista: 'Zheng DW, Henzinger MH. 2023. Multiplicative auction algorithm for approximate
    maximum weight bipartite matching. International Conference on Integer Programming
    and Combinatorial Optimization. IPCO: Integer Programming and Combinatorial Optimization,
    LNCS, vol. 13904, 453–465.'
  mla: Zheng, Da Wei, and Monika H. Henzinger. “Multiplicative Auction Algorithm for Approximate
    Maximum Weight Bipartite Matching.” <i>International Conference on Integer Programming
    and Combinatorial Optimization</i>, vol. 13904, Springer Nature, 2023, pp. 453–65,
    doi:<a href="https://doi.org/10.1007/978-3-031-32726-1_32">10.1007/978-3-031-32726-1_32</a>.
  short: D.W. Zheng, M.H. Henzinger, in:, International Conference on Integer Programming
    and Combinatorial Optimization, Springer Nature, 2023, pp. 453–465.
conference:
  end_date: 2023-06-23
  location: Madison, WI, United States
  name: 'IPCO: Integer Programming and Combinatorial Optimization'
  start_date: 2023-06-21
date_created: 2023-07-16T22:01:11Z
date_published: 2023-05-22T00:00:00Z
date_updated: 2023-07-18T07:08:51Z
day: '22'
department:
- _id: MoHe
doi: 10.1007/978-3-031-32726-1_32
ec_funded: 1
external_id:
  arxiv:
  - '2301.09217'
intvolume: '     13904'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2301.09217
month: '05'
oa: 1
oa_version: Preprint
page: 453-465
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: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
  grant_number: 'P33775 '
  name: Fast Algorithms for a Reactive Network Layer
publication: International Conference on Integer Programming and Combinatorial Optimization
publication_identifier:
  eissn:
  - 1611-3349
  isbn:
  - '9783031327254'
  issn:
  - 0302-9743
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Multiplicative auction algorithm for approximate maximum weight bipartite matching
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 13904
year: '2023'
...