SSLD
一种图着色启发式算法，通过半定规划（SDP）预处理单色类来改进DSATUR，利用Lovász theta数的谱几何信息选取高质量初始色类，是首个通过固定色类预处理改进DSATUR的方法
时间轴 (近 90 天)
SSLD（Semidefinite Spectral Learning with DSATUR）是一篇发布于arXiv（arXiv:2609.17633）的论文提出的新方法，通过在DSATUR开始前用半定规划预置一个高质量的第一色类，再交由DSATUR完成剩余顶点着色
SSLD用于求解第一色类的半定规划与计算Lovász theta数的半定规划类似
作者称据其所知SSLD是首个通过固定色类预处理来改进DSATUR的方法
SSLD在超过1600个基准实例上进行了对比评测，覆盖DIMACS测试集、Erdős–Rényi、Watts–Strogatz、Barabási–Albert三类随机图模型以及频率分配和作业车间调度实例
SSLD在几乎所有情形下都能匹配或超越DSATUR的着色质量，同时也明显优于朴素的GISD基线（不使用SDP指导的单色类预处理）
SSLD的运行时间约为DSATUR的195倍
如果着色质量是硬约束而计算时间相对宽裕，SSLD值得使用；如果追求极致速度，原始DSATUR是更务实的选择
SSLD体现了将连续优化（SDP/谱方法）与离散启发式相结合的思路：用SDP从全局把握图结构，再用DSATUR做局部快速决策
作者将SSLD定位为方向性验证而非即用型工具，认为SDP引导的第一色类预处理是值得深入探索的改进路径
全部知识事实 (9)
作者将SSLD定位为方向性验证而非即用型工具，认为SDP引导的第一色类预处理是值得深入探索的改进路径
50%待验证SSLD用于求解第一色类的半定规划与计算Lovász theta数的半定规划类似
50%待验证作者称据其所知SSLD是首个通过固定色类预处理来改进DSATUR的方法
50%待验证SSLD在超过1600个基准实例上进行了对比评测，覆盖DIMACS测试集、Erdős–Rényi、Watts–Strogatz、Barabási–Albert三类随机图模型以及频率分配和作业车间调度实例
50%待验证SSLD在几乎所有情形下都能匹配或超越DSATUR的着色质量，同时也明显优于朴素的GISD基线（不使用SDP指导的单色类预处理）
50%待验证SSLD的运行时间约为DSATUR的195倍
50%待验证如果着色质量是硬约束而计算时间相对宽裕，SSLD值得使用；如果追求极致速度，原始DSATUR是更务实的选择
50%待验证SSLD体现了将连续优化（SDP/谱方法）与离散启发式相结合的思路：用SDP从全局把握图结构，再用DSATUR做局部快速决策
50%待验证SSLD（Semidefinite Spectral Learning with DSATUR）是一篇发布于arXiv（arXiv:2609.17633）的论文提出的新方法，通过在DSATUR开始前用半定规划预置一个高质量的第一色类，再交由DSATUR完成剩余顶点着色
50%