Improved Pass Complexity for Semi-Streaming Matching in General Graphs via Budgeted Price Approach
En palabras de los autores
We present a simple deterministic semi-streaming algorithm that computes a -approximate maximum matching in general graphs in passes. This matches the pass complexity of the auction algorithm of Assadi, Liu, and Tarjan~[SOSA'21] for bipartite graphs, and answers Open Question~2 of Assadi~[SOSA'24 & TheoretiCS'25]. Our approach, which we call the budgeted price approach, is very different from the previous -pass semi-streaming algorithms for -approximation of matching in general graphs and improves their pass complexity. All previous approaches are augmenting-path-based and use passes by Fischer, Mitrovi\'{c}, and Uitto~[STOC'22], passes by Mitrovi\'{c}, Mukherjee, Sankowski, and Sheu~[ICALP'25], and passes by Izumi, Kitamura, and Yamaguchi~['25].
Apareció: lunes, 19 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 11 pages