首个用SDP预处理颜色类的DSATUR改进法，1600+实例几乎全面超越，代价是慢195倍
One Color Preprocessing Improves DSATUR
📖 AI 总结
本文提出一种名为SSLD（Semidefinite Spectral Learning with DSATUR）的新方法，用于改进图着色问题中广泛使用的DSATUR启发式算法。其核心思路是在DSATUR完成剩余着色之前，先通过求解一个类似计算Lovász theta数的半定规划（SDP），预处理出一个高质量的颜色类。作者称这是首个通过固定颜色类预处理来改进DSATUR的方法。研究在DIMACS实例、多种随机图（Erdős–Rényi、Watts–Strogatz、Barabási–Albert）、频率分配和作业车间调度等超过1600个基准实例上进行评估，结果显示SSLD在几乎所有情况下都能匹配或超越DSATUR，并优于朴素的单颜色类预处理基线，证实了SDP引导选择首个颜色类的价值。代价是运行时间约为DSATUR的195倍，但这一结果表明确保质量的首颜色类预处理是未来改进的一个可行方向。
🔑 关键词速览
| DSATUR | 一种基于饱和度（已着色邻居颜色数）优先选择下一个顶点的贪心图着色启发式算法，速度快但用色数通常偏多。 |
| SSLD | 本文提出的方法，全称Semidefinite Spectral Learning with DSATUR，先用半定规划预处理出一个颜色类，再让DSATUR完成剩余着色。 |
| 半定规划（SDP） | 一种凸优化问题，其变量为半正定矩阵，常用于图论中计算Lovász theta数等松弛界。 |
| Lovász theta数 | 由图谱定义的图不变量，位于团数与色数之间，可通过半定规划计算，用于近似图着色。 |
| 颜色类 | 图着色中具有相同颜色的顶点集合，必须构成独立集（内部无边）。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅