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