{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,18]],"date-time":"2026-08-18T01:42:15Z","timestamp":1787017335277,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":25,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["UK (EPSRC) Grant EP\/S03353X\/1"],"award-info":[{"award-number":["UK (EPSRC) Grant EP\/S03353X\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585252","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T13:34:20Z","timestamp":1684244060000},"page":"254-266","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":9,"title":["Sublinear Algorithms for (1.5+\ud835\udf16)-Approximate Matching"],"prefix":"10.1145","author":[{"given":"Sayan","family":"Bhattacharya","sequence":"first","affiliation":[{"name":"University of Warwick, UK"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Kiss","sequence":"additional","affiliation":[{"name":"University of Warwick, UK \/ MPI-INF, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thatchaphol","family":"Saranurak","sequence":"additional","affiliation":[{"name":"University of Michigan, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"45th International Colloquium on Automata, Languages, and Programming, ICALP 2018","author":"Adamaszek Anna","year":"2018","unstructured":"Anna Adamaszek , Matthias Mnich , and Katarzyna Paluch . 2018 . New Approximation Algorithms for (1, 2)-TSP. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018 , July 9-13, 2018, Prague, Czech Republic. Anna Adamaszek, Matthias Mnich, and Katarzyna Paluch. 2018. New Approximation Algorithms for (1, 2)-TSP. In 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic."},{"key":"e_1_3_2_1_2_1","volume-title":"Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs. In SODA.","author":"Assadi Sepehr","year":"2019","unstructured":"Sepehr Assadi , MohammadHossein Bateni , Aaron Bernstein , Vahab S. Mirrokni , and Clif Stein . 2019 . Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs. In SODA. Sepehr Assadi, MohammadHossein Bateni, Aaron Bernstein, Vahab S. Mirrokni, and Clif Stein. 2019. Coresets Meet EDCS: Algorithms for Matching and Vertex Cover on Massive Graphs. In SODA."},{"key":"e_1_3_2_1_3_1","unstructured":"Sepehr Assadi and Soheil Behnezhad. 2021. Beating Two-Thirds For RandomOrder Streaming Matching. In ICALP. Sepehr Assadi and Soheil Behnezhad. 2021. Beating Two-Thirds For RandomOrder Streaming Matching. In ICALP."},{"key":"e_1_3_2_1_4_1","unstructured":"Sepehr Assadi and Aaron Bernstein. 2019. Towards a Unified Theory of Sparsification for Matching Problems. In SOSA. Sepehr Assadi and Aaron Bernstein. 2019. Towards a Unified Theory of Sparsification for Matching Problems. In SOSA."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Soheil Behnezhad. 2021. Time-Optimal Sublinear Algorithms for Matching and Vertex Cover. In FOCS. Soheil Behnezhad. 2021. Time-Optimal Sublinear Algorithms for Matching and Vertex Cover. In FOCS.","DOI":"10.1109\/FOCS52979.2021.00089"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00089"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Soheil Behnezhad. 2023. Dynamic Algorithms for Maximum Matching Size. In SODA. Soheil Behnezhad. 2023. Dynamic Algorithms for Maximum Matching Size. In SODA.","DOI":"10.1137\/1.9781611977554.ch6"},{"key":"e_1_3_2_1_8_1","volume-title":"Beating Greedy Matching in Sublinear Time. arXiv preprint arXiv:2206.13057 ( 2023 ). To appear in SODA","author":"Behnezhad Soheil","year":"2023","unstructured":"Soheil Behnezhad , Mohammad Roghani , Aviad Rubinstein , and Amin Saberi . 2023. Beating Greedy Matching in Sublinear Time. arXiv preprint arXiv:2206.13057 ( 2023 ). To appear in SODA 2023 . Soheil Behnezhad, Mohammad Roghani, Aviad Rubinstein, and Amin Saberi. 2023. Beating Greedy Matching in Sublinear Time. arXiv preprint arXiv:2206.13057 ( 2023 ). To appear in SODA 2023."},{"key":"e_1_3_2_1_9_1","unstructured":"Aaron Bernstein. 2020. Improved Bounds for Matching in Random-Order Streams. In ICALP. Aaron Bernstein. 2020. Improved Bounds for Matching in Random-Order Streams. In ICALP."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Aaron Bernstein and Clif Stein. 2015. Fully Dynamic Matching in Bipartite Graphs. In ICALP. Aaron Bernstein and Clif Stein. 2015. Fully Dynamic Matching in Bipartite Graphs. In ICALP.","DOI":"10.1007\/978-3-662-47672-7_14"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Aaron Bernstein and Clif Stein. 2016. Faster Fully Dynamic Matchings with Small Approximation Ratios. In SODA. Aaron Bernstein and Clif Stein. 2016. Faster Fully Dynamic Matchings with Small Approximation Ratios. In SODA.","DOI":"10.1137\/1.9781611974331.ch50"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Sayan Bhattacharya Peter Kiss Thatchaphol Saranurak and David Wajc. 2023. Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time. In SODA. Sayan Bhattacharya Peter Kiss Thatchaphol Saranurak and David Wajc. 2023. Dynamic Matching with Better-than-2 Approximation in Polylogarithmic Update Time. In SODA.","DOI":"10.1137\/1.9781611977554.ch5"},{"key":"e_1_3_2_1_13_1","unstructured":"Yu Chen Sampath Kannan and Sanjeev Khanna. 2020. Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation. In ICALP. Yu Chen Sampath Kannan and Sanjeev Khanna. 2020. Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation. In ICALP."},{"key":"e_1_3_2_1_14_1","unstructured":"Yu Chen Sanjeev Khanna and Zihan Tan. 2022. Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics. CoRR ( 2022 ). Yu Chen Sanjeev Khanna and Zihan Tan. 2022. Sublinear Algorithms and Lower Bounds for Estimating MST and TSP Cost in General Metrics. CoRR ( 2022 )."},{"key":"e_1_3_2_1_15_1","series-title":"SIAM J. Comput. ( 2009 )","volume-title":"Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time","author":"Czumaj Artur","unstructured":"Artur Czumaj and Christian Sohler . 2009. Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time . SIAM J. Comput. ( 2009 ) . Artur Czumaj and Christian Sohler. 2009. Estimating the Weight of Metric Minimum Spanning Trees in Sublinear Time. SIAM J. Comput. ( 2009 )."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Fabrizio Grandoni Chris Schwiegelshohn Shay Solomon and Amitai Uzrad. 2022. Maintaining an EDCS in General Graphs: Simpler Density-Sensitive and with Worst-Case Time Bounds. In SOSA. Fabrizio Grandoni Chris Schwiegelshohn Shay Solomon and Amitai Uzrad. 2022. Maintaining an EDCS in General Graphs: Simpler Density-Sensitive and with Worst-Case Time Bounds. In SOSA.","DOI":"10.1137\/1.9781611977066.2"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"crossref","unstructured":"Michael Kapralov Slobodan Mitrovi\u0107 Ashkan Norouzi-Fard and Jakab Tardos. 2020. Space eficient approximation to maximum matching size from uniform edge samples. In SODA. Michael Kapralov Slobodan Mitrovi\u0107 Ashkan Norouzi-Fard and Jakab Tardos. 2020. Space eficient approximation to maximum matching size from uniform edge samples. In SODA.","DOI":"10.1137\/1.9781611975994.107"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Peter Kiss. 2022. Deterministic Dynamic Matching in Worst-Case Update Time. In ITCS. Peter Kiss. 2022. Deterministic Dynamic Matching in Worst-Case Update Time. In ITCS.","DOI":"10.1007\/s00453-023-01151-x"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Tobias M\u00f6mke and Ola Svensson. 2016. Removing and Adding Edges for the Traveling Salesman Problem. J. ACM ( 2016 ). Tobias M\u00f6mke and Ola Svensson. 2016. Removing and Adding Edges for the Traveling Salesman Problem. J. ACM ( 2016 ).","DOI":"10.1145\/2739008"},{"key":"e_1_3_2_1_20_1","unstructured":"Marcin Mucha. 2014. 13 \/9-Approximation for Graphic TSP. Theory Comput. Syst. ( 2014 ). Marcin Mucha. 2014. 13 \/9-Approximation for Graphic TSP. Theory Comput. Syst. ( 2014 )."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Huy N Nguyen and Krzysztof Onak. 2008. Constant-time approximation algorithms via local improvements. In FOCS. Huy N Nguyen and Krzysztof Onak. 2008. Constant-time approximation algorithms via local improvements. In FOCS.","DOI":"10.1109\/FOCS.2008.81"},{"key":"e_1_3_2_1_22_1","unstructured":"Krzysztof Onak Dana Ron Michal Rosen and Ronitt Rubinfeld. 2012. A nearoptimal sublinear-time algorithm for approximating the minimum vertex cover size. In SODA. SIAM. Krzysztof Onak Dana Ron Michal Rosen and Ronitt Rubinfeld. 2012. A nearoptimal sublinear-time algorithm for approximating the minimum vertex cover size. In SODA. SIAM."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.04.040"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"crossref","unstructured":"Andr\u00e1s Seb\u00f6 and Jens Vygen. 2014. Shorter tours by nicer ears: 7\/5-Approximation for the graph-TSP journal = Comb. 3\/2 for the path version and 4\/3 for twoedge-connected subgraphs. ( 2014 ). Andr\u00e1s Seb\u00f6 and Jens Vygen. 2014. Shorter tours by nicer ears: 7\/5-Approximation for the graph-TSP journal = Comb. 3\/2 for the path version and 4\/3 for twoedge-connected subgraphs. ( 2014 ).","DOI":"10.1007\/s00493-014-2960-3"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/110828691"}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","location":"Orlando FL USA","acronym":"STOC '23","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585252","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585252","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T12:47:02Z","timestamp":1750164422000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585252"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":25,"alternative-id":["10.1145\/3564246.3585252","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585252","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}