拟阵交中增广是否有凸性,以及几个其它相关问题
  • 板块学术版
  • 楼主xtx1092515503
  • 当前回复2
  • 已保存回复2
  • 发布时间2023/9/7 22:00
  • 上次更新2023/11/2 22:23:56
查看原帖
拟阵交中增广是否有凸性,以及几个其它相关问题
123369
xtx1092515503楼主2023/9/7 22:00

在一批(?)题目中,常常需要对于每个大小求出求出拟阵交中最优的独立集。这时一个常见的解法是,直接把拟阵交中每一次增广的结果作为答案。这是否表明,拟阵交的结果关于每次增广是凸的?也即,以最大权拟阵为例,每次增量都是逐渐递减的?(最小权拟阵在这种问题中是不是要转成对偶再处理啊?)

这个问题已询问两位 IOI Au 选手,并得到模糊不清的肯定回答。这里请求严谨的,不管是肯定还是否定的回答。如果是否定的话,额外询问上述算法的正确性证明,因为我所知的拟阵交算法的证明依赖于 minmax 定理,但是这个每次独立集大小扩大一的解法显然不能用 minmax 定理证明。

还有一个问题是,在 18 年论文中,提到带权拟阵交求 最大权 独立集时,要求的是 最短路,但是事实上你随便举一个例子(比如说取集合 {1,2}\{1,2\} 上的拟阵 {1},{2}\{1\},\{2\},且 w(1)=1,w(2)=2w(1)=1,w(2)=2,让这个拟阵同自己求交,就会发现按照最短路会取 {1}\{1\},但是答案是 {2}\{2\}。个人觉得这应该是论文有误(发论文是不是没人审稿啊()

2023/9/7 22:00
加载中...