在一批(?)题目中,常常需要对于每个大小求出求出拟阵交中最优的独立集。这时一个常见的解法是,直接把拟阵交中每一次增广的结果作为答案。这是否表明,拟阵交的结果关于每次增广是凸的?也即,以最大权拟阵为例,每次增量都是逐渐递减的?(最小权拟阵在这种问题中是不是要转成对偶再处理啊?)
这个问题已询问两位 IOI Au 选手,并得到模糊不清的肯定回答。这里请求严谨的,不管是肯定还是否定的回答。如果是否定的话,额外询问上述算法的正确性证明,因为我所知的拟阵交算法的证明依赖于 minmax 定理,但是这个每次独立集大小扩大一的解法显然不能用 minmax 定理证明。
还有一个问题是,在 18 年论文中,提到带权拟阵交求 最大权 独立集时,要求的是 最短路,但是事实上你随便举一个例子(比如说取集合 {1,2} 上的拟阵 {1},{2},且 w(1)=1,w(2)=2,让这个拟阵同自己求交,就会发现按照最短路会取 {1},但是答案是 {2}。个人觉得这应该是论文有误(发论文是不是没人审稿啊()