algorithm - 解释 0-extension 算法

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-extension 的目标是最小化具有不同颜色端点的边的总加权成本，而不是最大化它，因此 0-extension 实际上是一个聚类问题而不是着色问题。我通常怀疑使用聚类算法进行着色会产生良好的结果。如果您想要具有理论保证的东西，您可以研究 MAXCUT 问题的近似值（如果有两种以上的颜色，则实际上是一种概括），但我怀疑局部搜索算法在实践中会更好地工作。