最小割问题要求将无向加权图的节点划分为两块，使割边的权重和最小。近年来，我们针对该问题实现了一系列高速算法。当前最快的精确算法结合了一个近似算法以获得更紧的上界、基于该上界的归约、改进的数据结构以及并行收缩例程，已在开源包 VieCut 中发布，在真实数据上相较于之前的最快求解器顺序提升最高 2.5 倍，并行时最高 12.9 倍。
本文引入了“Agentic Algorithm Engineering (AAE)” 方法，即让自主的大语言模型代理在已有代码库上执行算法工程循环：提出运行时间瓶颈的假设、实现相应改动、在固定实例集上进行基准测试，并决定保留或舍弃该改动。尽管我们已经手工对算法进行了大量调优，代理仍发现了显著的优化，尤其在 DIMACS 核心实例上表现突出：在真实世界的 k‑core 上顺序提升 1.28 倍，32 线程提升 1.63 倍；在 DIMACS 核心实例上分别提升 6.26 倍和 127 倍。
点评