Title :
A Local Search Approximation Algorithm for Max-k-Cut of Graph and Hypergraph
Author :
Zhu, Wenxing ; Guo, Chuanyin
Author_Institution :
Center for Discrete Math. & Theor. Comput. Sci., Fuzhou Univ., Fuzhou, China
Abstract :
Given a graph or hyper graph, the graph or hyper graph Max-k-Cut problem is to partition the vertices into k nonempty sets such that the sum of weights of edges across different sets is maximized. We present a deterministic local search algorithm for the problem, which has a performance ratio 1 - 1/k for Max-k-Cut of graph, and has a similar result for Max-k-Cut of hyper graph.
Keywords :
approximation theory; graph theory; search problems; deterministic local search algorithm; graph; hypergraph; local search approximation algorithm; max-k-cut problem; Approximation algorithms; Approximation methods; Optimized production technology; Partitioning algorithms; Polynomials; Programming; Search problems; Max-k-Cut; approximation ratio; local search;
Conference_Titel :
Parallel Architectures, Algorithms and Programming (PAAP), 2011 Fourth International Symposium on
Conference_Location :
Tianjin
Print_ISBN :
978-1-4577-1808-3
DOI :
10.1109/PAAP.2011.35
