Объясните алгоритм 0-расширения

Question

Я пытаюсь реализовать алгоритм расширения 0.

Он используется для раскраски графа рядом цветов, где некоторым узлам уже назначен цвет и где каждое ребро имеет расстояние. Алгоритм вычисляет назначение цветов так, чтобы соседние узлы с одинаковым цветом имели как можно большее расстояние между ними.

Я нашел эту статью, объясняющую алгоритм: http://citeseer.ist.psu.edu/viewdoc/download;jsessionid=1FBA2D22588CABDAA8ECF73B41BD3D72?doi=10.1.1.100.8049&rep=rep1&type=pdf но я не вижу, как мне нужно реализовать Это.

Я уже задавал этот вопрос на сайте "теоретической информатики", но на полпути обсуждения мы вышли за рамки сайта: https://cstheory.stackexchange.com/questions/6163/explain-0-extension-algorithm

Кто-нибудь может объяснить этот алгоритм с точки зрения непрофессионала? Я планирую сделать окончательный код с открытым исходным кодом в пакете jgrapht.

Answer 1

Цель 0-расширения состоит в том, чтобы минимизировать суммарную взвешенную стоимость ребер с разными конечными точками цвета, а не максимизировать ее, поэтому 0-расширение на самом деле является проблемой кластеризации, а не проблемой раскраски. Я вообще скептически отношусь к тому, что использование алгоритма кластеризации для окрашивания даст хорошие результаты. Если вы хотите что-то с теоретической гарантией, вы можете посмотреть приближения к задаче MAXCUT (действительно, обобщение, если есть более двух цветов), но я подозреваю, что алгоритм локального поиска будет работать лучше на практике.