给定两个集合E和S，元素的集合E和E的子集的集合S，求出S的子集C，使得C中所有集合的并等于E，同时使得|C|最小。这就是经典的集合覆盖问题（SCP）。它是NP-hard类的最优化组合问题。对于NP-HARD类的问题，在P≠NP的假设下，是不存在多项式时间算法的，只能设计求解他们的近似算法或近似方案，或者对于问题条件进行限制使得限制后的子问题是一个非NP-HARD类的问题。 集合覆盖问题在实际应用中有好多变型。若对于任意的s∈S有一个权重w（s），并且同样求c，使得sum from s∈C w（s）最小。问题就成为了带有权重的集合覆盖问题。若对于任意s∈S有一个限制正整数k（s），使得在s中的至多覆盖k（s）个元素，问题就成为带容量限制的集合覆盖问题（CSCP），可以看出带权重或带容量限制的集合覆盖问题至少和集合覆盖问题一样难。Lang和Yannakanis证明了集合覆盖问题不存在c（lnn），c＜1／4的近似算法，除非NP（?）Dtime(n^Polylogn)。Feige改进了这个结果证明集合覆盖问题不存在好于（1-ε）ln|s|近似比的多项式时间近似算法，ε＞0，除非NP（?）Dtime(n^polylogn)，这是我们所知最新的反面结果。 带容量限制的集合覆盖问题是近年来集合覆盖算法与复杂性研究的热点，在实践中比一般集合覆盖更具价值。集合覆盖实用子问题的算法与复杂性多年来一直是计算机科学研究者攻克集合覆盖问题的工作重点。Papadimitriou，Yannakakis证明即使每个元素在S中出现常数B（≥2）次的集合覆盖问题亦是NP-Hard且为APX-Hard，Bar-Yehuda与Even给出树路径可表示的集合覆盖问题近似度为2的多项式时间近似算法。