SSLD: SDP-препроцессинг ускоряет DSATUR для раскраски графов

Проблема классического DSATUR

Проблема раскраски графов (GCP) является NP-трудной, и эвристика DSATUR долгое время оставалась одним из самых быстрых методов решения. Однако у нее есть существенный недостаток: она часто использует больше цветов, чем современные state-of-the-art алгоритмы. Авторы работы — Адам Нуира и Лукас Исенманн — предлагают решение, которое сохраняет скорость DSATUR, но улучшает качество результата за счет предварительной обработки.

Методология: SSLD и SDP

Новый алгоритм, названный SSLD (Semidefinite Spectral Learning with DSATUR), вводит концепцию «одного цвета» (One Color Preprocessing). Перед запуском основной эвристики SSLD использует полуопределенное программирование (SDP), аналогичное тому, что применяется для вычисления числа Ловаша, чтобы выделить первый хороший класс цветов. Этот шаг позволяет зафиксировать оптимальную начальную структуру, которую затем дополняет DSATUR.

Результаты на бенчмарках

Эксперименты проводились на более чем 1600 тестовых экземплярах, включая стандарты DIMACS, случайные графы (Erdős–Rényi, Watts–Strogatz, Barabási–Albert), а также задачи назначения частот и планирования цехов. Результаты показывают, что SSLD либо совпадает с DSATUR, либо превосходит его в подавляющем большинстве случаев, подтверждая ценность SDP-направленного выбора первого цвета.

Значение для индустрии

Хотя увеличение времени вычисления в 195 раз является существенным компромиссом, авторы демонстрируют, что направление SDP-препроцессинга первого цвета является перспективным. Это открывает путь для создания более эффективных гибридных алгоритмов, где тяжелые вычисления на этапе подготовки компенсируются улучшением качества решения и, потенциально, ускорением основного этапа раскраски.

Источник: arXiv cs.AI ↗