An Optimisation Algorithm for Maximum Independent Set with Applications in Map Labelling
An Optimisation Algorithm for Maximum Independent Set with Applications in Map Labelling
复制标题
最大独立集优化算法及其在地图标注中的应用
DOI：
10.1007/3-540-48481-7_37
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
K. Aardal
中科院分区：
文献类型：
--
作者：
B. Verweij;K. Aardal
我们考虑以下地图标记问题：给定不同点p1，p2，...，pn，找到一组成对不相交的轴平行正方形Q1，Q2，.，其中pi是Qi的角。本文提出了一个求图的最大独立集的分支和割算法，并将其应用于图标号中的独立集实例。该算法使用了一种新的技术，用于设置变量的分支和绑定树，隐含地利用欧几里德性质的独立集的问题所产生的地图标签。计算实验表明，该技术有助于控制分支和边界树的大小。我们还提出了一个新的变种的算法产生违反奇洞不等式。使用我们的算法，我们可以找到可证明的最佳解决方案的地图标签的实例，最多950个城市在适度的计算时间，一个相当大的改进，在文献中报道的结果。
We consider the following map labelling problem: given distinct points p1, p2, ..., pn in the plane, find a set of pairwise disjoint axis-parallel squares Q1,Q2, ..., Qn where pi is a corner of Qi. This problem reduces to that of finding a maximum independent set in a graph.We present a branch and cut algorithm for finding maximum independent sets and apply it to independent set instances arising from map labelling. The algorithm uses a new technique for setting variables in the branch and bound tree that implicitly exploits the Euclidean nature of the independent set problems arising from map labelling. Computational experiments show that this technique contributes to controlling the size of the branch and bound tree. We also present a novel variant of the algorithm for generating violated odd-hole inequalities. Using our algorithm we can find provably optimal solutions for map labelling instances with up to 950 cities within modest computing time, a considerable improvement over the results reported on in the literature.