Optimization Online


Local Search Approximation Algorithms for the Complement of the Min-$k$-Cut Problems

Wenxing Zhu (wxzhu2000***at***yahoo.com.cn)
Chuanyin Guo (wxzhu2000***at***yahoo.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


Entry Submitted: 07/07/2010
Entry Accepted: 07/08/2010
Entry Last Modified: 07/09/2010

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society