The Complement of Hypergraph Capacitated Min-k-Cut Problem

摘要

The capacitated min-k-cut problem of hypergraphis the problem of partitioning the vertices into k parts, and each part has a different capacity. The objective is to minimize the weight of cut hyper edges. It is an NP-hard problem which is an important problem with extensive applications to many areas, such as VLSI CAD, image segmentation, etc. Although many heuristic algorithms have been developed, to the best of our knowledge, no approximation algorithm is known for such problem. We present a local search algorithm for hyper graph capacitated min-k-cut problem, using the idea of complement. The algorithm achieves a competitive approximation factor of 1/(1+s/2(k-1)), where s is the largest cardinality of all hyper edges. We also extend the algorithm and get an approximate result for hyper graph capacitated max-k-cut problem.