Journal article
Approximation algorithms for maximization problems arising in graph partitioning
Journal of Algorithms, Vol.41(2), pp.174-211
Nov/2001
Abstract
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 subset of or equal to 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 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 kappa, then one can select in polynomial time a set of kappa vertices that covers over 80% of the edges. (C) 2001 Elsevier Science.
Details
- Title
- Approximation algorithms for maximization problems arising in graph partitioning
- Creators
- Uriel Feige (null) - 972WIS_INST___83M Langberg (null)
- Resource Type
- Journal article
- Publication Details
- Journal of Algorithms, Vol.41(2), pp.174-211; Nov/2001
- Number of pages
- 38
- Language
- English
- DOI
- https://doi.org/10.1006/jagm.2001.1183
- Record Identifier
- 993263846403596
Metrics
7 Record Views