Scholarlink

<p>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 <b>CGOPT 2.0</b> to obtain high-quality low-dimensional embeddings. The continuous solutions are then mapped to 2-way partitions via hyperplane rounding, while general <i>k</i>-way partitions are constructed recursively, maintaining both partition quality and scalability. On the theoretical side, leveraging <b>CGOPT 2.0</b>, we prove that the objective function of the constructed continuous model satisfies the KŁ 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

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

  • 期刊论文

  • 发表日期：

    2026年5月28日

查看全文
  • Yingying Li,
  • Zexian Liu,
  • Yongqiang Yao,
  • Hongwei Liu

摘要

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Ł 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.