An improved rounding method and semidefinite programming relaxation for graph partition
From MaRDI portal
Publication:1849503
DOI10.1007/s101070100288zbMath1008.90042MaRDI QIDQ1849503
Yinyu Ye, Qiaoming Han, Jia-Wei Zhang
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
90C22: Semidefinite programming
90C27: Combinatorial optimization
49M25: Discrete approximations in optimal control
Related Items
Torification and factorization of birational maps, Algebraic cuts, 𝜋₁ of Hamiltonian 𝑆¹ manifolds, Approximating the 2-catalog segmentation problem using semidefinite programming relaxations, Geometric invariant theory and flips, Improved approximation algorithms for maximum graph partitioning problems, Approximate \(k\)-Steiner forests via the Lagrangian relaxation technique with internal preprocessing, Approximation algorithms for MAX RES CUT with limited unbalanced constraints, On approximation of max-vertex-cover, Improved approximations for max set splitting and max NAE SAT, Approximation algorithm for MAX DICUT with given sizes of parts, The densest \(k\)-subgraph problem on clique graphs, Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation, A continuation algorithm for max-cut problem
