  


Local Search Approximation Algorithms for the Complement of the Min$k$Cut Problems
Wenxing Zhu (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 nonnegative 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 NPhard for $k \geq 3$, and the capacitated min$k$cut problem is also NPhard 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/2010 Modify/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  