Graph partitioning using linear and semidefinite programming

DOI10.1007/S10107-002-0342-XzbMath1030.90079OpenAlexW2043471141MaRDI QIDQ1411631

Franz Rendl, Abdel Lisser

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

Mathematics Subject Classification ID

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 (29)

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 ⋮ IPRSDP: a primal-dual interior-point relaxation algorithm for semidefinite programming ⋮ 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

This page was built for publication: Graph partitioning using linear and semidefinite programming