Approximation Algorithms for Maximization Problems Arising in Graph Partitioning

✍ Scribed by Uriel Feige; Michael Langberg

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 261 KB
• Volume: 41
• Category: Article
• ISSN: 0196-6774
• DOI: 10.1006/jagm.2001.1183

✦ Synopsis

Given a graph G = V E , a weight function w E → R + , and a parameter k, we consider the problem of finding a subset U ⊆ V of size k that maximizes: Max-Vertex Cover k the weight of edges incident with vertices in U, Max-Dense Subgraph k the weight of edges in the subgraph induced by U, Max-Cut k the weight of edges cut by the partition U V \ U , Max-Uncut k the weight of edges not cut by the partition U V \ U .

For each of the above problems we present approximation algorithms based on semidefinite programming and obtain approximation ratios better than those previously published. In particular we show that if a graph has a vertex cover of size k, then one can select in polynomial time a set of k vertices that covers over 80% of the edges.