Approximation algorithms for max cut and max bisection problems using semidefinite programming relaxations

DOI10.15960/J.CNKI.ISSN.1007-6093.2016.03.003MaRDI QIDQ5282656zbMATH OpenFDO

Authors Ting Sun, Gai-Di Li, Wen-Qing Xu

Publication date 14 July 2017

Full work available at URL https://doi.org/10.15960/J.CNKI.ISSN.1007-6093.2016.03.003

zbMATH Keywords

approximation algorithmmax bisection problemmax cut problemsemidefinite programming

Mathematics Subject Classification ID

Semidefinite programming (90C22) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Improved approximation algorithms for MAX k-CUT and MAX BISECTION
• Improved approximation algorithms for MAX k-cut and MAX BISECTION
• .878-approximation algorithms for MAX CUT and MAX 2SAT
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• scientific article; zbMATH DE number 2063458

Cited in

(29)

• A tight semidefinite relaxation of the MAX CUT problem
• An improved rounding method and semidefinite programming relaxation for graph partition
• An SDP randomized approximation algorithm for max hypergraph cut with limited unbalance
• An improved semidefinite programming hierarchies rounding approximation algorithm for maximum graph bisection problems
• An improved approximation algorithm for the \(2\)-catalog segmentation problem using semidefinite programming relaxation
• Improved semidefinite bounding procedure for solving max-cut problems to optimality
• Approximation bounds for quadratic maximization and max-cut problems with semidefinite programming relaxation
• Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition
• Rank-two relaxation heuristics for MAX-CUT and other binary quadratic programs
• .878-approximation algorithms for MAX CUT and MAX 2SAT
• A Complex Semidefinite Programming Rounding Approximation Algorithm for the Balanced Max-3-Uncut Problem
• Improved approximation of Max-Cut on graphs of bounded degree
• scientific article; zbMATH DE number 5734227 (Why is no real title available?)
• Approximation Algorithms for Semidefinite Packing Problems with Applications to Maxcut and Graph Coloring
• scientific article; zbMATH DE number 1302192 (Why is no real title available?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• scientific article; zbMATH DE number 2063458 (Why is no real title available?)
• scientific article; zbMATH DE number 1754595 (Why is no real title available?)
• A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems
• Near-optimal approximation algorithm for simultaneous Max-Cut
• An Improved Semidefinite Programming Hierarchies Rounding Approximation Algorithm for Maximum Graph Bisection Problems
• scientific article; zbMATH DE number 7525500 (Why is no real title available?)
• Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
• Complex semidefinite programming and Max-\(k\)-Cut
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• scientific article; zbMATH DE number 6401405 (Why is no real title available?)
• Approximating CSPs with global cardinality constraints using SDP hierarchies
• A .699-approximation algorithm for Max-Bisection.
• Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations

This page was built for publication: Approximation algorithms for max cut and max bisection problems using semidefinite programming relaxations

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