Engineering Kernelization for Maximum Cut
Engineering Kernelization for Maximum Cut
复制标题
DOI：
10.1137/1.9781611976007.3
复制
发表时间：
2019-05
期刊：
影响因子：
--
通讯作者：
D. Ferizović;Demian Hespe;S. Lamm;Matthias Mnich;Christian Schulz;Darren Strash
中科院分区：
文献类型：
--
作者：
D. Ferizović;Demian Hespe;S. Lamm;Matthias Mnich;Christian Schulz;Darren Strash
核化（Kernelization）是一个通用的理论框架，用于通过重复应用数据约简规则将NP难问题的实例预处理为具有有限大小的（通常较小）实例。对于基本的最大割问题，核化算法在理论上对于各种参数化都是高效的。然而，这些归约规则在实践中的功效--帮助解决极具挑战性的基准实例以达到最优--仍然完全未被探索。我们设计了一套新的高效的数据简化规则，submassive大多数以前发布的规则，并证明其对基准数据集的显着影响，包括合成实例，以及来自VLSI和图像分割应用领域的数据集。我们的实验表明，当前最先进的求解器可以加快高达多个数量级时，结合我们的数据减少规则。特别是在社交和生物网络上，核化使我们能够解决四个以前在十小时内无法解决的问题，其中三个问题现在在不到两秒的时间内解决了。
Kernelization is a general theoretical framework for preprocessing instances of NP-hard problems into (generally smaller) instances with bounded size, via the repeated application of data reduction rules. For the fundamental Max Cut problem, kernelization algorithms are theoretically highly efficient for various parameterizations. However, the efficacy of these reduction rules in practice---to aid solving highly challenging benchmark instances to optimality---remains entirely unexplored. We engineer a new suite of efficient data reduction rules that subsume most of the previously published rules, and demonstrate their significant impact on benchmark data sets, including synthetic instances, and data sets from the VLSI and image segmentation application domains. Our experiments reveal that current state-of-the-art solvers can be sped up by up to multiple orders of magnitude when combined with our data reduction rules. On social and biological networks in particular, kernelization enables us to solve four instances that were previously unsolved in a ten-hour time limit with state-of-the-art solvers; three of these instances are now solved in less than two seconds.