Comment by sebzim4500

Yeah you can approximate up to an arbitrary factor in close to linear time. See [1]

[1] https://drops.dagstuhl.de/storage/01oasics/oasics-vol061_sos...