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

DOI10.1007/S10957-023-02195-3zbMATH Open1519.90207OpenAlexW4360998224MaRDI QIDQ6103705FDOQ6103705

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

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

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

zbMATH Keywords

branch-and-boundmax-cutsparsity pattern

Mathematics Subject Classification ID

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

Cites Work

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

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)