研究人員提出了一種名為SSLD的演算法，來優化圖形的著色

研究人員提出SSLD (Semidefinite Spectral Learning with DSATUR)，這是一種新的數據預處理方法，能夠提高經典的DSATUR啟發式算法解決圖形著色問題（GCP）的效率。

該方法基於使用半定程式設計 (SDP)選擇第一類顏色，然後再運行主要算法。與標準方法不同，SSLD鎖定初始節點集，這使得最終圖形著色的質量得到顯著改善，同時最小化使用的顏色總數。

該算法的效率已在超過1600個基準測試中進行了測試，包括埃爾德什-雷尼圖、瓦茨-斯特羅加茨圖和巴拉巴西-阿爾伯特圖，以及頻率分配和生產規劃任務。結果表明，SSLD在所有測試案例中都優於或與標準的DSATUR相當。

該方法的主要限制是計算複雜性：預處理過程使算法的執行速度約比原始的DSATUR慢195倍。然而，作者確認使用SDP引導的第一類顏色選擇是一個有前途的方向，用于進一步優化NP難問題。

該工作在arXiv上發表，展示了混合方法的潛力，結合經典的啟發式方法和數學程式設計方法來解決複雜的組合問題。