Advertisement
Published in:
2017 | OriginalPaper | Chapter
An Efficient Algorithm for Judicious Partition of Hypergraphs
Authors : Tunzi Tan, Jihong Gui, Sainan Wang, Suixiang Gao, Wenguo Yang
Published in: Combinatorial Optimization and Applications
Publisher: Springer International Publishing
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Abstract
Judicious partition of hypergraphs \(\mathcal {H}\)=(V, H) is to optimize several quantities simultaneously, and the goal of this paper is to partition the vertex set V into K parts: \(\{V_1,V_2,\dots ,V_K\}\) so as to minimize the \(\max \{L(V_1),L_(V_2),\dots ,L(V_K)\}\), where \(L(V_j)\) is the number of hyperedges incident to the part \(V_j(\mathcal {H})\). The bounds for the objective function are given and the relationship between the maximum hyperdegree and the objective value is analyzed. Before giving an efficient algorithm for the judicious partition of hypergraphs, a sub-problem is obtained, which is proved to be an unweighted set cover problem, apart from a tiny difference. A greedy algorithm is applied to solve the sub-problem. Last but not least, the judicious partition of hypergraphs is successfully divided into a series of sub-problems and an efficient algorithm is developed for the original problem.