An improved rounding method and semidefinite programming relaxation for graph partition

DOI10.1007/s101070100288zbMath1008.90042OpenAlexW2032321507MaRDI QIDQ1849503

Qiaoming Han, Jia-Wei Zhang, Yinyu Ye

Publication date: 1 December 2002

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s101070100288

Mathematics Subject Classification ID

Semidefinite programming (90C22) Combinatorial optimization (90C27) Discrete approximations in optimal control (49M25)

Related Items

Improved approximating \(2\)-CatSP for \(\sigma\geq 0.50\) with an unbalanced rounding matrix ⋮ An improved approximation algorithm for the \(2\)-catalog segmentation problem using semidefinite programming relaxation ⋮ Improved approximations for max set splitting and max NAE SAT ⋮ Approximation algorithm for MAX DICUT with given sizes of parts ⋮ Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing ⋮ A continuation algorithm for max-cut problem ⋮ An approximation algorithm for the balanced Max-3-Uncut problem using complex semidefinite programming rounding ⋮ Graph bisection revisited ⋮ Finding connected \(k\)-subgraphs with high density ⋮ On semidefinite programming relaxations of maximum \(k\)-section ⋮ Solving \(k\)-cluster problems to optimality with semidefinite programming ⋮ Floer cohomology and flips ⋮ Finding Connected Dense $$k$$-Subgraphs ⋮ Uniform \(K\)-stability, Duistermaat-Heckman measures and singularities of pairs ⋮ The densest \(k\)-subgraph problem on clique graphs ⋮ Matroid-constrained vertex cover ⋮ Torification and factorization of birational maps ⋮ An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem ⋮ Geometric invariant theory and flips ⋮ Combining clustered adaptive multistart and discrete dynamic convexized method for the max-cut problem ⋮ Functorial factorization of birational maps for qe schemes in characteristic 0 ⋮ Approximating \(k\)-generalized connectivity via collapsing HSTs ⋮ Approximating the 2-catalog segmentation problem using semidefinite programming relaxations ⋮ Algebraic cuts ⋮ Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation ⋮ A discrete dynamic convexized method for the max-cut problem ⋮ Approximation algorithms for MAX RES CUT with limited unbalanced constraints ⋮ An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance ⋮ 𝜋₁ of Hamiltonian 𝑆¹ manifolds ⋮ Relaxations of Combinatorial Problems Via Association Schemes ⋮ Threshold-based preprocessing for approximating the weighted dense \(k\)-subgraph problem ⋮ 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 ⋮ Equivariant multiplicities of simply-laced type flag minors ⋮ Improved approximation algorithms for maximum graph partitioning problems ⋮ An improved semidefinite programming hierarchies rounding approximation algorithm for maximum graph bisection problems