Approximating Red-Blue Set Cover

02/01/2023

∙

by   Eden Chlamtáč, et al.

∙

0

∙

share

We provide a new approximation algorithm for the Red-Blue Set Cover problem and give a new hardness result. Our approximation algorithm achieves Õ(m^1/3)-approximation improving on the Õ(m^1/2)-approximation due to Elkin and Peleg (where m is the number of sets). Additionally, we provide a nearly approximation preserving reduction from Min k-Union to Red-Blue Set Cover that gives an Ω̃(m^1/4 - ε) hardness under the Dense-vs-Random conjecture.