Constraint hypergraph partitioning problems via recursive bipartition algorithm based on improved Dai-Kou conjugate gradient algorithm

doi:10.1007/s10589-026-00795-z

Constraint hypergraph partitioning problems via recursive bipartition algorithm based on improved Dai-Kou conjugate gradient algorithm

2026-05-01

0

PRE

AI

DOI：10.1007/s10589-026-00795-z

原文链接

原文求助

摘要

En 中文

本文提出了一种整合图和超图结构的分层超图划分框架。在分层求解过程中，初始划分阶段并行生成多个候选划分并独立优化，最终选择最佳解。该策略有效降低了算法陷入局部最优的风险，提高了解的稳定性和鲁棒性。对于初始划分，将离散超图问题转化为连续无约束优化模型，利用现有求解器CGOPT 2.0高效求解，获得高质量低维嵌入。连续解通过超平面舍入映射为二分划分，而一般k分划分则递归构造，兼顾划分质量和可扩展性。在理论方面，借助CGOPT 2.0，证明所构建连续模型的目标函数满足K-性质，并进一步推导出函数值和迭代序列的显式收敛率，为非凸设置下的可靠性和数值稳定性提供严格保证。在ISPD98和Titan23等公开基准上的全面实验表明，本算法在割规模质量上总体优于KaHyPar、hMetis、K-SpecPart、Mt-KaHyPar和PaToH，运行时间相当或略高，消融研究进一步验证了各创新组件的有效性。

Keyword:

Hypergraph partitioning

Recursive bipartition

Parallel technology

Unconstrained optimization

Constraint hypergraph partitioning problems via recursive bipartition algorithm based on improved Dai-Kou conjugate gradient algorithm

摘要

期刊

机构

引用论文