经典的最大覆盖(MC)问题是一个 NP 难优化问题。考虑 d 个元素 U = {e1, e2, ... ed} 和 c 集 T1, T2 ... Tc。每个集合都包含 U 中的一些元素。问题的目标是找到最多 b 个集合，使得这些集合的并集的基数最大化。 例如，T1={e1,e3}，T2={e1,e2,e3}，T3={e3,e4}。当b=2时，最优解选择T2和T3。 我正在考虑经典 MC 问题的变体，它施加了集合大小约束。如果所有集合的大小都以 k 为界，则考虑 1 < k <= d。将此问题称为k-MC。问题仍然是 NP 难题吗？
我的猜想是，k-MC 仍然是 NP 难问题，但我正在努力从已证明的 NP 难问题(如 MC)中提出多项式约简。 对于最大覆盖的任意实例，如果我可以找到所有 k>1 的问题的多项式约简，我可以得出结论，我的问题也是 NP 困难的。 这是我到目前为止得到的:
- 当 k=d 时，该问题基本上等同于经典的最大覆盖率。
- 当 k=d-1 时，我们查看给定的 MC 实例，看看是否存在大小为 d 的集合。如果有，只需选择它即可。否则，它会简化为 k=d-1 的 k-MC 问题。
当k小于d-1时，我采用动态规划来完成约简。然而，这会产生非多项式时间减少，这违背了从 NP 难问题中减少时间的目的。
如果有人能给我一些关于如何解决这个问题的指示，或者只是对k-MC(P或NP)的问题复杂性做出有根据的猜测，我真的会欣赏它。
最佳答案
2-MC 很简单——将大小为 2 的集合解释为图，并对非二分图运行您最喜欢的匹配算法。一旦超过匹配基数，您就只能选择单例。
3-MC很难。您可以对 3-partition 的实例进行编码作为 3-MC，将集合作为与目标相加的三元组，然后通过检查 b = n/3 的覆盖范围来确定它是否可解。
关于algorithm - 具有集合大小约束(P 或 NP)的最大覆盖问题的问题复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/60536639/