Graph partitioning using linear and semidefinite programming
From MaRDI portal
Publication:1411631
DOI10.1007/s10107-002-0342-xzbMath1030.90079OpenAlexW2043471141MaRDI QIDQ1411631
Publication date: 29 October 2003
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10107-002-0342-x
Applications of graph theory (05C90) Semidefinite programming (90C22) Linear programming (90C05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)
Related Items
SDP-based bounds for graph partition via extended ADMM, Matrix Relaxations in Combinatorial Optimization, An overview of graph covering and partitioning, The Ratio-Cut Polytope and K-Means Clustering, Facial reduction algorithms for conic optimization problems, Size-constrained graph partitioning polytopes, On semidefinite programming relaxations of maximum \(k\)-section, Semidefinite approximations for quadratic programs over orthogonal matrices, ILP-Based Local Search for Graph Partitioning, An efficient heuristic for the \(k\)-partitioning problem, The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp>, Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems, Multi-way clustering and biclustering by the ratio cut and normalized cut in graphs, Balanced graph partitioning based on mixed 0-1 linear programming and iteration vertex relocation algorithm, An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem, Robust optimization of graph partitioning involving interval uncertainty, A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem, Linear and quadratic programming approaches for the general graph partitioning problem, Optimal price zones of electricity markets: a mixed-integer multilevel model and global solution approaches, A Mehrotra predictor-corrector interior-point algorithm for semidefinite optimization, The robust binomial approach to chance-constrained optimization problems with application to stochastic partitioning of large process networks, Contribution of copositive formulations to the graph partitioning problem, Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints, SDP Relaxations for Some Combinatorial Optimization Problems, A new full-Newton step \(O(n)\) infeasible interior-point algorithm for semidefinite optimization, Unnamed Item, Spectral bounds for graph partitioning with prescribed partition sizes, Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition
