62 citations · 82 across the 23 of their papers we have counts for
Showing 2022Show all
2 papers · 1 filter
cs.DS2022
Growing a Random Maximal Independent Set Produces a 2-approximate Vertex Cover
Nate Veldt
This paper presents a fast and simple new 2-approximation algorithm for minimum weighted vertex cover. The unweighted version of this algorithm is equivalent to a well-known greedy…
cs.DS2022★ 1 cited
Optimal LP Rounding and Linear-Time Approximation Algorithms for Clustering Edge-Colored Hypergraphs
Nate Veldt
We study the approximability of an existing framework for clustering edge-colored hypergraphs, which is closely related to chromatic correlation clustering and is motivated by mach…