<p>We explore the well-known max hypergraph bisection problem, which is widely used in fields such as very large-scale integration layout design, network planning, biological networks and quantum computing. Given a hypergraph <i>H</i> = (<i>V</i>, <i>E</i>, <i>ω</i>) with a non-negative weight function <i>ω</i>: <i>E</i> → ℝ<sub>⩾0</sub>, the goal is to find a balanced partition (<i>V</i><sub>1</sub>, <i>V</i><sub>2</sub>) while maximizing the total weight of hyperedges crossing different vertex subsets. For this purpose, we relax the max hypergraph bisection problem using the Lasserre hierarchy semidefinite programming. Then we design a new approximation algorithm combining random hyperplane and perturbation, and analyze the approximation factor via reducing dimensions and using interval arithmetic. Finally, we prove that if all hyperedges contain at least 3 vertices, the approximation factor is 0.7728; otherwise, the approximation factor is 0.6818. To the best of our knowledge, these results are the current best ones.</p>

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

An improved SDP rounding approximation algorithm for the max hypergraph bisection

  • Guangfeng Li,
  • Gregory Z. Gutin,
  • Deren Han,
  • Jian Sun,
  • Xiaoyan Zhang

摘要

We explore the well-known max hypergraph bisection problem, which is widely used in fields such as very large-scale integration layout design, network planning, biological networks and quantum computing. Given a hypergraph H = (V, E, ω) with a non-negative weight function ω: E → ℝ⩾0, the goal is to find a balanced partition (V1, V2) while maximizing the total weight of hyperedges crossing different vertex subsets. For this purpose, we relax the max hypergraph bisection problem using the Lasserre hierarchy semidefinite programming. Then we design a new approximation algorithm combining random hyperplane and perturbation, and analyze the approximation factor via reducing dimensions and using interval arithmetic. Finally, we prove that if all hyperedges contain at least 3 vertices, the approximation factor is 0.7728; otherwise, the approximation factor is 0.6818. To the best of our knowledge, these results are the current best ones.