algorithm - 3 近似算法（随机或确定）

Question

让 3 多彩套问题。给定 M 个大小为 3 的集合，超过 {1...n} 个元素。换句话说，给定集合 S1, S2, ... , Sm 其中，对于每个 i，对于某些 x, y, z ∈ {1, ... , n}，Si = {x, y, z}。我想要找到的是选择一组元素 E ⊆ {1, ... , n} 以便最大化在 E 中恰好包含一个元素的集合的数量，即最大化 |{i |Si ∩电子| = 1}| . 解决方案可以使用 3 个近似多项式时间算法。

我正在考虑一种随机算法，以保证近似比率或确定性比率。我有一些想法，但我不确定如何实际实施。任何帮助，将不胜感激。

标签： algorithmcomplexity-theoryapproximationdeterministic