The Library
Sublinear algorithms for (1.5+\epsilon)-approximate matching
Tools
Bhattacharya, Sayan, Kiss, Peter and Saranurak, Thatchaphol (2023) Sublinear algorithms for (1.5+\epsilon)-approximate matching. In: STOC 2023: 55th Annual ACM Symposium on Theory of Computing, Orlando, Florida, 20-23 Jun 2023. Published in: STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing pp. 254-266. ISBN 9781450399135. doi:10.1145/3564246.3585252
|
PDF
WRAP-sublinear-algorithms-approximate-matching-Bhattacharya-2023.pdf - Accepted Version - Requires a PDF viewer. Download (1798Kb) | Preview |
Official URL: https://doi.org/10.1145/3564246.3585252
Abstract
We study sublinear time algorithms for estimating the size of maximum matching. After a long line of research, the problem was finally settled by Behnezhad [FOCS’22], in the regime where one is willing to pay an approximation factor of 2. Very recently, Behnezhad et al. [SODA’23] improved the approximation factor to (2−1/2O(1/γ)) using n1+γ time. This improvement over the factor 2 is, however, minuscule and they asked if even 1.99-approximation is possible in n2−Ω(1) time.
We give a strong affirmative answer to this open problem by showing (1.5+є)-approximation algorithms that run in n2−Θ(є2) time. Our approach is conceptually simple and diverges from all previous sublinear-time matching algorithms: we show a sublinear time algorithm for computing a variant of the edge-degree constrained subgraph (EDCS), a concept that has previously been exploited in dynamic [Bernstein Stein ICALP’15, SODA’16], distributed [Assadi et al. SODA’19] and streaming [Bernstein ICALP’20] settings, but never before in the sublinear setting.
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Series Name: | STOC 2023 | ||||||
Journal or Publication Title: | STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing | ||||||
Publisher: | ACM | ||||||
ISBN: | 9781450399135 | ||||||
Official Date: | 2 June 2023 | ||||||
Dates: |
|
||||||
Page Range: | pp. 254-266 | ||||||
DOI: | 10.1145/3564246.3585252 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Reuse Statement (publisher, data, author rights): | © ACM, 2023. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC 2023). Association for Computing Machinery, New York, NY, USA, 254–266. https://doi.org/10.1145/3564246.3585252 | ||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||
Date of first compliant deposit: | 14 April 2023 | ||||||
Date of first compliant Open Access: | 20 July 2023 | ||||||
RIOXX Funder/Project Grant: |
|
||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | STOC 2023: 55th Annual ACM Symposium on Theory of Computing | ||||||
Type of Event: | Conference | ||||||
Location of Event: | Orlando, Florida | ||||||
Date(s) of Event: | 20-23 Jun 2023 | ||||||
Related URLs: | |||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year