An improved rounding method and semidefinite programming relaxation for graph partition |
| |
Authors: | Qiaoming Han Yinyu Ye Jiawei Zhang |
| |
Institution: | (1) School of Mathematics and Computer Science, Nanjing Normal University, Nanjing, 210097, P.R. China, CN;(2) Department of Management Sciences, Henry B. Tippie College of Business, The University of Iowa, Iowa City, IA 52242, USA, US |
| |
Abstract: | Given an undirected graph G=(V,E) with |V|=n and an integer k between 0 and n, the maximization graph partition (MAX-GP) problem is to determine a subset S⊂V of k nodes such that an objective function w(S) is maximized. The MAX-GP problem can be formulated as a binary quadratic program and it is NP-hard. Semidefinite programming
(SDP) relaxations of such quadratic programs have been used to design approximation algorithms with guaranteed performance
ratios for various MAX-GP problems. Based on several earlier results, we present an improved rounding method using an SDP
relaxation, and establish improved approximation ratios for several MAX-GP problems, including Dense-Subgraph, Max-Cut, Max-Not-Cut,
and Max-Vertex-Cover.
Received: March 10, 2000 / Accepted: July 13, 2001?Published online February 14, 2002 |
| |
Keywords: | : Dense-k-Subgraph – Max-Cut – Max-Not-Cut – Max-Vertex-Cover – polynomial approximation algorithm – performance ratio – semidefinite programming |
本文献已被 SpringerLink 等数据库收录! |
|