A new global algorithm for max-cut problem with chordal sparsity
From MaRDI portal
Publication:6103705
DOI10.1007/s10957-023-02195-3zbMath1519.90207OpenAlexW4360998224MaRDI QIDQ6103705
Zhi-bin Deng, Wen-Xun 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
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Quadratic programming (90C20) Combinatorial optimization (90C27)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Positive definite completions of partial Hermitian matrices
- Minimal triangulations of graphs: a survey
- Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations
- Using a mixed integer quadratic programming solver for the unconstrained quadratic \(0-1\) problem
- Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
- A two-level graph partitioning problem arising in mobile wireless communications
- A MAX-CUT formulation of 0/1 programs
- Solving the max-cut problem using eigenvalues
- 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
- Exploiting sparsity in complex polynomial optimization
- A computational study of exact subgraph based SDP bounds for max-cut, stable set and coloring
- COSMO: a conic operator splitting method for convex conic problems
- Chordal decomposition in operator-splitting methods for sparse semidefinite programs
- Set-completely-positive representations and cuts for the max-cut polytope and the unit modulus lifting
- Improved semidefinite bounding procedure for solving max-cut problems to optimality
- Exploiting Sparsity in Semidefinite Programming via Matrix Completion I: General Framework
- Second order cone programming relaxation of nonconvex quadratic optimization problems
- Rank-Two Relaxation Heuristics for MAX-CUT and Other Binary Quadratic Programs
- Advanced Scatter Search for the Max-Cut Problem
- BiqCrunch
- Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
- Facets of the Bipartite Subgraph Polytope
- Complexity of Finding Embeddings in a k-Tree
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Randomized heuristics for the Max-Cut problem
- A NEW SECOND-ORDER CONE PROGRAMMING RELAXATION FOR MAX-CUT PROBLEMS
- On the cut polytope
- Exact Facetial Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization
- 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
- Sums of Squares and Semidefinite Program Relaxations for Polynomial Optimization Problems with Structured Sparsity
- Finding Low-rank Solutions of Sparse Linear Matrix Inequalities using Convex Optimization
