Sepehr Assadi - A Simple $(1-ε)$-Approximation Semi-Streaming Algorithm for Maximum (Weighted) Matching

theoretics:13451 - TheoretiCS, August 1, 2025, Volume 4 - https://doi.org/10.46298/theoretics.25.16
A Simple $(1-ε)$-Approximation Semi-Streaming Algorithm for Maximum (Weighted) MatchingArticle

Authors: Sepehr Assadi ORCID

    We present a simple semi-streaming algorithm for $(1-ε)$-approximation of bipartite matching in $O(\log{\!(n)}/ε)$ passes. This matches the performance of state-of-the-art "$ε$-efficient" algorithms -- the ones with much better dependence on $ε$ albeit with some mild dependence on $n$ -- while being considerably simpler. The algorithm relies on a direct application of the multiplicative weight update method with a self-contained primal-dual analysis that can be of independent interest. To show case this, we use the same ideas, alongside standard tools from matching theory, to present an equally simple semi-streaming algorithm for $(1-ε)$-approximation of weighted matchings in general (not necessarily bipartite) graphs, again in $O(\log{\!(n)}/ε)$ passes.


    Volume: Volume 4
    Published on: August 1, 2025
    Accepted on: February 7, 2025
    Submitted on: April 23, 2024
    Keywords: Data Structures and Algorithms,Distributed, Parallel, and Cluster Computing

    Consultation statistics

    This page has been seen 37 times.
    This article's PDF has been downloaded 17 times.