Approximation of dense-\(n/2\)-subgraph and the complement of min-bisection

DOI10.1023/A:1021390231133zbMath1047.90041OpenAlexW1498543354MaRDI QIDQ1810886

Jia-Wei Zhang, Yinyu Ye

Publication date: 9 June 2003

Published in: Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/a:1021390231133

zbMATH Keywords

Semidefinite programmingDense-\(k\)-subgraphMin-bisectionPolynomial approximation algorithm

Mathematics Subject Classification ID

Semidefinite programming (90C22) Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25)

Related Items (14)

Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix ⋮ Approximation algorithm for MAX DICUT with given sizes of parts ⋮ Approximation and hardness results for the max \(k\)-uncut problem ⋮ Projection algorithms for nonconvex minimization with application to sparse principal component analysis ⋮ Approximation and Hardness Results for the Max k-Uncut Problem ⋮ New algorithms for a simple measure of network partitioning ⋮ A semidefinite programming approach to the hypergraph minimum bisection problem ⋮ Approximating the 2-catalog segmentation problem using semidefinite programming relaxations ⋮ New algorithms for a simple measure of network partitioning ⋮ Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph ⋮ Approximating max \(k\)-uncut via LP-rounding plus greed, with applications to densest \(k\)-subgraph ⋮ On approximation of max-vertex-cover ⋮ On solving the densestk-subgraph problem on large graphs ⋮ Improved approximation algorithms for maximum graph partitioning problems

This page was built for publication: Approximation of dense-\(n/2\)-subgraph and the complement of min-bisection