稀疏图上的重构
本文研究了在三种常见改变模式下的独立集重新配置问题,发现在 Token Jumping 或 Token addition/removal 模式下问题是 NP-complete,而在 Token Sliding 模式下问题仍然保持是 PSPACE-complete。
Jul, 2017
研究通过添加或删除至多 $l$ 个顶点,使得每个操作结果都是大小最多为 $k$ 的顶点覆盖的情况下,判断是否可以将给定的图 $G$ 中的一个顶点覆盖 $S$ 转换为另一个顶点覆盖 $T$。研究对问题在各种图类中的复杂性进行分类,其中表明该问题在二分图中仍然具有 W [1] -hard 度,在(正则的)度受限的图以及更普遍的稠度较小的图上为 NP-hard 但出于固定参数是可处理的,并且在树形图上和仙人掌图上(在某些其他限制下)是可多项式时间内可解决的。
Feb, 2014
我们提出了一种新的算法类别,即不变特征子空间恢复(ISR),用于实现分类和回归问题的可证明领域泛化。在二元分类方案中,我们的第一种算法 ISR-Mean 可以通过类条件分布的一阶矩来识别不变特征所张成的子空间,并在 $d_s+1$ 个训练环境下实现可证明的领域泛化。
Nov, 2023
本文提出了利用不变特征子空间恢复(ISR)实现域泛化的算法,ISR-Mean 和 ISR-Cov 可以从一阶和二阶矩中识别不变特征所涵盖的子空间并在训练集为 d_s+1 时实现可证明的域泛化,相比 Invariant Risk Minimization (IRM) , ISR 算法避免了非凸性问题,并具有全局收敛性保证,实验结果表明 ISR 算法在合成基准测试和图像与文本三个真实数据集上,都能作为简单但有效的后处理方法来提高训练模型对假冗余和组偏差的最坏情况准确性。
Jan, 2022
该论文研究了随机约束满足问题的解空间结构,并证明了在解消失之前,它们会组成指数数量的簇,并且每个簇都相对较小且相距较远。此外,每个簇内的大部分变量都被冻结,并提出 Survey Propagation 算法的一项重要假设。
Nov, 2006
我们提出了一种称为有界组合重新配置的方法,用于基于 Answer Set Programming(ASP)解决组合重新配置问题。我们设计和实现了有界组合重新配置,并提出了独立集重新配置问题的 ASP 编码,这是最研究的组合重新配置问题之一。通过考虑 CoRe Challenge 2022 的所有实例,我们进行了实证分析。
Jul, 2023
本研究介绍了一种基于递增稀疏化的算法,可在输入 n 个顶点和 m 条边的加权图以及一个值 k 后,产生一个有限边数为 n-1+m/k 的递增稀疏化图,较好地维持了图的条件数,并以很快的速度求解出满足一定误差要求的向量,这一算法基于 Chebyshev 迭代和递归算法实现。
Mar, 2010
本文研究了应用广泛的 NP-hard 问题之一,最大独立集问题( M IS),提出了局部搜索框架 ARIR 及其三种算法,采用三种不同的减少策略,在五组基准测试中显示出明显的优越性。
Aug, 2022
研究在使用 Reg-GXPath 表达式作为完整性约束的图形数据库中,基于数据值计算子集和超集的修复问题,发现在正面的 Reg-GXPath 碎片中,这些问题具有多项式时间算法,而语言的完整表现力使它们成为难以处理的问题。
Jun, 2022