.png){kind=icon}
Return
Constraint hypergraph partitioning problems via recursive bipartition algorithm based on improved Dai-Kou conjugate gradient algorithm
.png){kind=icon}
PRE
AI
DOI：10.1007/s10589-026-00795-z.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
This paper proposes a multilevel hypergraph partitioning framework that integrates both graph and hypergraph structures. In the multilevel solution process, multiple candidate partitions are generated in parallel during the initial partitioning stage and independently refined, with the best solution ultimately selected. This strategy effectively reduces the risk of the algorithm being trapped in local optima and improves solution stability and robustness. For the initial partitioning, the discrete hypergraph problem is transformed into a continuous unconstrained optimization model, which is efficiently solved by the existing solver CGOPT 2.0 to obtain high-quality low-dimensional embeddings. The continuous solutions are then mapped to 2-way partitions via hyperplane rounding, while general k-way partitions are constructed recursively, maintaining both partition quality and scalability. On the theoretical side, leveraging CGOPT 2.0, we prove that the objective function of the constructed continuous model satisfies the K & Lstrok; property and further derive explicit convergence rates for both the function value and iteration sequences, providing rigorous guarantees of reliability and numerical stability in nonconvex settings. Comprehensive experiments on public benchmarks such as ISPD98 and Titan23 demonstrate that our algorithm generally achieves superior cutsize quality compared to KaHyPar, hMetis, K-SpecPart, Mt-KaHyPar and PaToH, with comparable or slightly higher runtime, and ablation studies further validate the effectiveness of each novel component.
Keywords:
Hypergraph partitioning
Recursive bipartition
Parallel technology
Unconstrained optimization
Journal
C
IF:
2
Papers:
74
Citations:
3.5K
Organization
View more organizations
Cited Papers
No cited papers available