A new global algorithm for max-cut problem with chordal sparsity

DOI10.1007/S10957-023-02195-3MaRDI QIDQ6103705zbMATH OpenOpenAlexFDO

Authors Cheng Lu, Zhibin Deng, Shu-Cherng Fang, Wenxun Xing

Publication date 27 June 2023

Published in Journal of Optimization Theory and Applications (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10957-023-02195-3

zbMATH Keywords

branch-and-boundmax-cutsparsity pattern

Mathematics Subject Classification ID

Quadratic programming (90C20) Combinatorial optimization (90C27) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• A branch-and-bound algorithm for solving max-\(k\)-cut problem
• A Branch and Bound Algorithm for Max-Cut Based on Combining Semidefinite and Polyhedral Relaxations
• Improved semidefinite bounding procedure for solving max-cut problems to optimality
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• SpeeDP: an algorithm to compute SDP bounds for very large max-cut instances

Cites work

• A branch-and-price procedure for clustering data that are graph connected
• A computational study of exact subgraph based SDP bounds for max-cut, stable set and coloring
• A MAX-CUT formulation of 0/1 programs
• A NEW SECOND-ORDER CONE PROGRAMMING RELAXATION FOR MAX-CUT PROBLEMS
• A two-level graph partitioning problem arising in mobile wireless communications
• Advanced scatter search for the max-cut problem
• BiqCrunch: a semidefinite branch-and-bound method for solving binary quadratic problems
• Chordal decomposition in operator-splitting methods for sparse semidefinite programs
• Chordal-TSSOS: a moment-SOS hierarchy that exploits term sparsity with chordal extension
• Complexity of Finding Embeddings in a k-Tree
• COSMO: a conic operator splitting method for convex conic problems
• Exact Facetial Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization
• Exploiting sparsity in complex polynomial optimization
• Exploiting sparsity in semidefinite programming via matrix completion. I: General framework
• Facets of the Bipartite Subgraph Polytope
• Finding low-rank solutions of sparse linear matrix inequalities using convex optimization
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 6737879 (Why is no real title available?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Improved semidefinite bounding procedure for solving max-cut problems to optimality
• Minimal triangulations of graphs: a survey
• On the cut polytope
• Positive definite completions of partial Hermitian matrices
• Randomized heuristics for the Max-Cut problem
• Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs
• Second order cone programming relaxation of nonconvex quadratic optimization problems
• Set-completely-positive representations and cuts for the max-cut polytope and the unit modulus lifting
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
• Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
• Solving the max-cut problem using eigenvalues
• Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion
• Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
• Treewidth: computational experiments
• Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem
• What Works Best When? A Systematic Evaluation of Heuristics for Max-Cut and QUBO

This page was built for publication: A new global algorithm for max-cut problem with chordal sparsity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6103705)