---
OA_place: repository
OA_type: green
_id: '15121'
abstract:
- lang: eng
  text: We present an auction algorithm using multiplicative instead of constant weight
    updates to compute a (1-E)-approximate maximum weight matching (MWM) in a bipartite
    graph with n vertices and m edges in time 0(mE-1), beating the running time of
    the fastest known approximation algorithm of Duan and Pettie [JACM ’14] that runs
    in 0(mE-1 log E-1). Our algorithm is very simple and it can be extended to give
    a dynamic data structure that maintains a (1-E)-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 0(mE-1), where m is the sum of the number of initially existing
    and inserted edges.
acknowledgement: The first author thanks Chandra Chekuri for useful discussions about
  this paper. This work was done in part at the University of Vienna. 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.
article_processing_charge: No
article_type: original
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 M. Multiplicative auction algorithm for approximate maximum
    weight bipartite matching. <i>Mathematical Programming</i>. 2025;210:881-894.
    doi:<a href="https://doi.org/10.1007/s10107-024-02066-3">10.1007/s10107-024-02066-3</a>
  apa: Zheng, D. W., &#38; Henzinger, M. (2025). Multiplicative auction algorithm
    for approximate maximum weight bipartite matching. <i>Mathematical Programming</i>.
    Springer Nature. <a href="https://doi.org/10.1007/s10107-024-02066-3">https://doi.org/10.1007/s10107-024-02066-3</a>
  chicago: Zheng, Da Wei, and Monika Henzinger. “Multiplicative Auction Algorithm
    for Approximate Maximum Weight Bipartite Matching.” <i>Mathematical Programming</i>.
    Springer Nature, 2025. <a href="https://doi.org/10.1007/s10107-024-02066-3">https://doi.org/10.1007/s10107-024-02066-3</a>.
  ieee: D. W. Zheng and M. Henzinger, “Multiplicative auction algorithm for approximate
    maximum weight bipartite matching,” <i>Mathematical Programming</i>, vol. 210.
    Springer Nature, pp. 881–894, 2025.
  ista: Zheng DW, Henzinger M. 2025. Multiplicative auction algorithm for approximate
    maximum weight bipartite matching. Mathematical Programming. 210, 881–894.
  mla: Zheng, Da Wei, and Monika Henzinger. “Multiplicative Auction Algorithm for
    Approximate Maximum Weight Bipartite Matching.” <i>Mathematical Programming</i>,
    vol. 210, Springer Nature, 2025, pp. 881–94, doi:<a href="https://doi.org/10.1007/s10107-024-02066-3">10.1007/s10107-024-02066-3</a>.
  short: D.W. Zheng, M. Henzinger, Mathematical Programming 210 (2025) 881–894.
corr_author: '1'
date_created: 2024-03-17T23:00:58Z
date_published: 2025-03-01T00:00:00Z
date_updated: 2025-09-09T12:39:58Z
day: '01'
department:
- _id: MoHe
doi: 10.1007/s10107-024-02066-3
ec_funded: 1
external_id:
  arxiv:
  - '2301.09217'
  isi:
  - '001176048100003'
intvolume: '       210'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2301.09217
month: '03'
oa: 1
oa_version: Preprint
page: 881-894
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: Mathematical Programming
publication_identifier:
  eissn:
  - 1436-4646
  issn:
  - 0025-5610
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
related_material:
  record:
  - id: '13236'
    relation: earlier_version
    status: public
scopus_import: '1'
status: public
title: Multiplicative auction algorithm for approximate maximum weight bipartite matching
type: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 210
year: '2025'
...
---
OA_place: publisher
OA_type: hybrid
_id: '10045'
abstract:
- lang: eng
  text: "Given a fixed finite metric space (V,μ), the {\\em minimum 0-extension problem},
    denoted as 0-Ext[μ], is equivalent to the following optimization problem: minimize
    function of the form minx∈Vn∑ifi(xi)+∑ijcijμ(xi,xj) where cij,cvi are given nonnegative
    costs and fi:V→R are functions given by fi(xi)=∑v∈Vcviμ(xi,v). The computational
    complexity of 0-Ext[μ] has been recently established by Karzanov and by Hirai:
    if metric μ is {\\em orientable modular} then 0-Ext[μ] can be solved in polynomial
    time, otherwise 0-Ext[μ] is NP-hard. To prove the tractability part, Hirai developed
    a theory of discrete convex functions on orientable modular graphs generalizing
    several known classes of functions in discrete convex analysis, such as L♮-convex
    functions. We consider a more general version of the problem in which unary functions
    fi(xi) can additionally have terms of the form cuv;iμ(xi,{u,v}) for {u,v}∈F, where
    set F⊆(V2) is fixed. We extend the complexity classification above by providing
    an explicit condition on (μ,F) for the problem to be tractable. In order to prove
    the tractability part, we generalize Hirai's theory and define a larger class
    of discrete convex functions. It covers, in particular, another well-known class
    of functions, namely submodular functions on an integer lattice. Finally, we improve
    the complexity of Hirai's algorithm for solving 0-Ext on orientable modular graphs.\r\n"
acknowledgement: We thank the anonymous reviewers for their careful reading of our
  manuscript and their many insightful comments and suggestions. Open access funding
  provided by Institute of Science and Technology (IST Austria).
article_processing_charge: Yes (via OA deal)
article_type: original
arxiv: 1
author:
- first_name: Martin
  full_name: Dvorak, Martin
  id: 40ED02A8-C8B4-11E9-A9C0-453BE6697425
  last_name: Dvorak
  orcid: 0000-0001-5293-214X
- first_name: Vladimir
  full_name: Kolmogorov, Vladimir
  id: 3D50B0BA-F248-11E8-B48F-1D18A9856A87
  last_name: Kolmogorov
citation:
  ama: Dvorak M, Kolmogorov V. Generalized minimum 0-extension problem and discrete
    convexity. <i>Mathematical Programming</i>. 2025;209:279-322. doi:<a href="https://doi.org/10.1007/s10107-024-02064-5">10.1007/s10107-024-02064-5</a>
  apa: Dvorak, M., &#38; Kolmogorov, V. (2025). Generalized minimum 0-extension problem
    and discrete convexity. <i>Mathematical Programming</i>. Springer Nature. <a href="https://doi.org/10.1007/s10107-024-02064-5">https://doi.org/10.1007/s10107-024-02064-5</a>
  chicago: Dvorak, Martin, and Vladimir Kolmogorov. “Generalized Minimum 0-Extension
    Problem and Discrete Convexity.” <i>Mathematical Programming</i>. Springer Nature,
    2025. <a href="https://doi.org/10.1007/s10107-024-02064-5">https://doi.org/10.1007/s10107-024-02064-5</a>.
  ieee: M. Dvorak and V. Kolmogorov, “Generalized minimum 0-extension problem and
    discrete convexity,” <i>Mathematical Programming</i>, vol. 209. Springer Nature,
    pp. 279–322, 2025.
  ista: Dvorak M, Kolmogorov V. 2025. Generalized minimum 0-extension problem and
    discrete convexity. Mathematical Programming. 209, 279–322.
  mla: Dvorak, Martin, and Vladimir Kolmogorov. “Generalized Minimum 0-Extension Problem
    and Discrete Convexity.” <i>Mathematical Programming</i>, vol. 209, Springer Nature,
    2025, pp. 279–322, doi:<a href="https://doi.org/10.1007/s10107-024-02064-5">10.1007/s10107-024-02064-5</a>.
  short: M. Dvorak, V. Kolmogorov, Mathematical Programming 209 (2025) 279–322.
corr_author: '1'
date_created: 2021-09-27T10:48:23Z
date_published: 2025-01-01T00:00:00Z
date_updated: 2025-05-19T13:52:10Z
day: '01'
ddc:
- '004'
department:
- _id: GradSch
- _id: VlKo
doi: 10.1007/s10107-024-02064-5
external_id:
  arxiv:
  - '2109.10203'
  isi:
  - '001176563300001'
file:
- access_level: open_access
  checksum: 25d9bd490719b45eca84f4d93a06c69f
  content_type: application/pdf
  creator: dernst
  date_created: 2025-04-16T09:36:08Z
  date_updated: 2025-04-16T09:36:08Z
  file_id: '19578'
  file_name: 2025_MathProgramming_Dvorak.pdf
  file_size: 839510
  relation: main_file
  success: 1
file_date_updated: 2025-04-16T09:36:08Z
has_accepted_license: '1'
intvolume: '       209'
isi: 1
keyword:
- minimum 0-extension problem
- metric labeling problem
- discrete metric spaces
- metric extensions
- computational complexity
- valued constraint satisfaction problems
- discrete convex analysis
- L-convex functions
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '01'
oa: 1
oa_version: Published Version
page: 279-322
publication: Mathematical Programming
publication_identifier:
  eissn:
  - 1436-4646
  issn:
  - 0025-5610
publication_status: published
publisher: Springer Nature
quality_controlled: '1'
scopus_import: '1'
status: public
title: Generalized minimum 0-extension problem and discrete convexity
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: journal_article
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 209
year: '2025'
...