- Local Search Approximation Algorithms for the Complement of the Min-$k$-Cut Problems Wenxing Zhu (wxzhu2000yahoo.com.cn) Chuanyin Guo (wxzhu2000yahoo.com.cn) Abstract: Min-$k$-cut is the problem of partitioning vertices of a given graph or hypergraph into $k$ subsets such that the total weight of edges or hyperedges crossing different subsets is minimized. For the capacitated min-$k$-cut problem, each edge has a non-negative weight, and each subset has a possibly different capacity that imposes an upper bound on its size. The objective is to find a partition that minimizes the sum of edge weights on all pairs of vertices that lie in different subsets. The min-$k$-cut problem is NP-hard for $k \geq 3$, and the capacitated min-$k$-cut problem is also NP-hard for $k \geq 2$. Min-$k$-cut has numerous applications, for example, VLSI circuit partitioning, which is a key step in VLSI CAD. Although many heuristics have been proposed for min-$k$-cut problems, there are few approximation results of min-$k$-cut problems. We study the equivalent complement problem of the min-$k$-cut problem and extend the method proposed in \cite{gauer} to present deterministic local search approximation algorithms for the complement problem of the min-$k$-cut problem, and the complement problem of the capacitated min-$k$-cut problem on graph with performance ratio $\frac{1}{k}$. Keywords: min-$k$-cut, approximation algorithm, local search. Category 1: Combinatorial Optimization (Approximation Algorithms ) Citation: Research Report, Fuzhou University, CHINA. 2010.6.30 Download: Entry Submitted: 07/07/2010Entry Accepted: 07/08/2010Entry Last Modified: 07/09/2010Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society.