“Our main result is designing an algorithm that returns a vertex cover of G* with size at most (3/2+ϵ) times the expected size of the minimum vertex cover, using only O(n/ϵp) non-adaptive queries. This improves over the best-known 2-approximation algorithm by Behnezhad, Blum, and Derakhshan [SODA’22], who also show that Ω(n/p) queries are necessary to achieve any constant approximation.”

Read the paper and see the full list of authors in ArXiv.