CSCI3160 Special 13：集合覆盖贪心、反例与困难性

原件：Sp13 题目（本地课件） p.1。 每题先题解后解析；单词按字母集合处理，不把重复字母多算。

Problem 1：单词集合覆盖的具体输出

题解

收益相同按题目所列先后顺序选，得到thread、lost、drain、shun，新增字母数依次为6、3、2、1，覆盖全部12个字母。

具体解析

宇宙为{a,d,e,h,i,l,n,o,r,s,t,u}。thread覆盖a,d,e,h,r,t共6个，初始收益最大。之后尚缺i,l,n,o,s,u：lost新增l,o,s共3，shun也可新增s,u,n共3，按约定先选lost。

再剩i,n,u，drain新增i,n共2，shun新增n,u也有2，按题目顺序取drain。最后只剩u，只有shun含u，必须选它。最终并集可逐字核对。

若第二步选shun，后续输出可能不同，仍是合法贪心执行；题目未规定平局时不存在唯一集合序列。这里每轮重新计算的是尚未覆盖的新字母，不能一直按单词长度排序。例如最后thread原有6字母但收益已经0。

Problem 2：被选集合的当时收益非递增

题解

覆盖元素越来越多，所以任意未选集合的剩余收益只会不变或下降。第i轮最大收益为bᵢ，下一轮每个剩余集合的收益均≤它在第i轮的收益≤bᵢ，因此bᵢ₊₁≤bᵢ。

具体解析

要比较同一时刻的最大值，再利用每个候选自身的单调性。第i轮虽然删掉了刚选中的集合，但这只会减少候选，不会制造更大的收益。Q1序列6、3、2、1正是例子；非递增允许相等，不能证明成“每步严格下降”。

即使下一轮挑了完全不同的集合，它在上一轮也是候选，不会比上一轮赢家收益更高；而期间又只可能损失收益，这就补齐跨集合比较的逻辑。

Problem 3：贪心近似比不能由2界定

题解

构造16个“列集合”L₁,…,L₁₆，以及34个“横块集合”Rᵢⱼ。对每个i=2,…,16、j=1,…,floor(16/i)，创建i个不同宇宙元素(i,j,t)，其中t从i(j−1)+1到ij。Rᵢⱼ包含该块全部i个元素；Lₜ包含第三坐标为t的所有元素。贪心会选全部34个R，而选16个L已覆盖全部，所以比值至少34/16=2.125>2。

具体解析

每个元素既属于唯一横块Rᵢⱼ，也属于唯一列Lₜ。假设大于i的横层已全部选完，其元素均覆盖；此时第i层每个横块还剩i个新元素，同层不同块不交。而一个列集合在每一剩余层2,…,i至多有一个元素，收益至多i−1。于是贪心必选横块而不选列；同层其他横块收益不变，直至整层选完，再进入下一层。

右侧集合数是

这段比较是严格i>i−1，不靠有利的左右平局。OPT≤16已经够用：较小的OPT只会让实际比率更大。构造是Regular10最大度反例的关联集合版本，但此处已完整列出宇宙与集合，无需读另一文档才能复现。

跟踪构造的最后两层，检验“必选横块”的量词。 当只剩层 2、3 时，每个 3 元横块仍有收益 3，而每列在这两层最多各含一个元素，收益至多 2；所以先选完五个 3 元横块。随后八个 2 元横块各有收益 2，每列只剩至多 1，故继续选完它们。这个论证对每一次选块后的状态都成立，因为同层块互不相交；不是只证明每层开头那一步。

Problem 4：恰好k个集合的判定版本也难

题解

反设有多项式算法，给定集合族和k，能判断是否有恰好k个集合的覆盖，并在存在时返回它。对k=0,1,…,m依次调用，第一个成功的k就是最优值，返回的覆盖就是最优解。这将给出多项式最优集合覆盖算法，除非P=NP否则不可能。

具体解析

原集合族m个集合，其全体之并就是宇宙，因此最迟k=m一定成功；空宇宙可能在k=0成功。调用次数至多m+1，每次输入大小仍为原规模的多项式，乘起来依然多项式。

题目是“恰好k”，不是“至多k”，但顺次寻找首个成功值无需改变接口；若已有小覆盖，还可以添加未选集合扩成更大覆盖，因此在k≤m范围内也有通常单调性。不过不需要借助二分，就已经完成困难性归约。

Problem 5：列覆盖变成集合覆盖

题解

把n行作为宇宙元素；第j列形成集合Sⱼ={i:M[i,j]=1}。用最大新增覆盖数贪心选列，输出大小≤(1+ln n)OPT，因而为O(OPT log n)（n≥2）。

具体解析

每行至少一个1保证每个宇宙元素属于某个候选集合，实例可行。选列后每行至少一个所选位置为1，恰好等价于对应集合之并覆盖全部行，所以最优值保持。

自取三行四列矩阵为[1,1,0,0]、[0,1,1,0]、[0,0,0,1]，第2列覆盖前两行，第4列覆盖第三行；贪心选2、4即可。若把列当宇宙、行当集合，就解成另一个问题了。

朴素实现每轮重算m列对n行的收益，最多n轮，O(n²m)，已是多项式。对数保证来自未覆盖z行中，某个最优列至少覆盖z/OPT行。n=1时log1=0，精确写法应保留1+ln n或用log(n+1)，不能把单行实例的非零输出界写成0。

来源与证据

Sp13 p.1；Q1收益序列、Q3的34个横块已程序核对。题解均为自行推导。