Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming

DOI10.1016/J.JCSS.2003.07.012zbMath1093.90038OpenAlexW4230348051MaRDI QIDQ1887719

Michel X. Goemans, David P. Williamson

Publication date: 22 November 2004

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2003.07.012

zbMATH Keywords

Semidefinite programmingApproximation algorithmsMaximum cut

Mathematics Subject Classification ID

Semidefinite programming (90C22) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (28)

An approximation algorithm for the balanced Max-3-Uncut problem using complex semidefinite programming rounding ⋮ On approximating complex quadratic optimization problems via semidefinite programming relaxations ⋮ New NP-Hardness Results for 3-Coloring and 2-to-1 Label Cover ⋮ A class of spectral bounds for max \(k\)-cut ⋮ Unnamed Item ⋮ An approximation algorithm for maxk-uncut with capacity constraints ⋮ A maximum hypergraph 3-cut problem with limited unbalance: approximation and analysis ⋮ Approximation algorithms for indefinite complex quadratic maximization problems ⋮ Approximating projections by quantum operations ⋮ New semidefinite relaxations for a class of complex quadratic programming problems ⋮ Geometry and optimization in quantum information. Abstracts from the workshop held October 3--9, 2021 (hybrid meeting) ⋮ A semidefinite relaxation based global algorithm for two-level graph partition problem ⋮ A VNS metaheuristic with stochastic steps for Max 3-cut and Max 3-section ⋮ The capacitated max \(k\)-cut problem ⋮ Tightness of a New and Enhanced Semidefinite Relaxation for MIMO Detection ⋮ A branch-and-bound algorithm for solving max-\(k\)-cut problem ⋮ Mixed-integer programming techniques for the connected max-\(k\)-cut problem ⋮ Argument division based branch-and-bound algorithm for unit-modulus constrained complex quadratic programming ⋮ Conic stability of polynomials and positive maps ⋮ Tightness of the maximum likelihood semidefinite relaxation for angular synchronization ⋮ Frequency-hopping code design for Target detection via optimization theory ⋮ Semidefinite relaxations for partitioning, assignment and ordering problems ⋮ Invariant Semidefinite Programs ⋮ Phase recovery, MaxCut and complex semidefinite programming ⋮ Semidefinite relaxations for partitioning, assignment and ordering problems ⋮ A combinatorial algorithm for MAX CSP ⋮ Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem ⋮ Unnamed Item

Uses Software

• Outward rotations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
• The ellipsoid method and its consequences in combinatorial optimization
• Geometric algorithms and combinatorial optimization
• Linear systems in Jordan algebras and primal-dual interior-point algorithms
• On approximate graph colouring and MAX-\(k\)-CUT algorithms based on the \(\vartheta\)-function
• A New Way of Using Semidefinite Programming with Applications to Linear Equations mod p
• Outward rotations
• Convex quadratic and semidefinite programming relaxations in scheduling
• Approximate graph coloring by semidefinite programming
• On the Shannon capacity of a graph
• A Geometric Approach to Betweenness
• The Chebyshev Polynomials of a Matrix
• Derandomizing Approximation Algorithms Based on Semidefinite Programming
• Barrier Functions in Interior Point Methods
• Self-Scaled Barriers and Interior-Point Methods for Convex Programming
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Primal-Dual Interior-Point Methods for Self-Scaled Cones
• Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
• Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming

This page was built for publication: Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming