Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
type: Item
instance of: scholarly article
title: Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
zbMATH Open document ID: 1093.90038
author: Michel X. Goemans
author: David P. Williamson
published in: Journal of Computer and System Sciences
publication date: 2004-11-22T00:00:00Z
Mathematics Subject Classification ID: 90C22
Mathematics Subject Classification ID: 90C27
Mathematics Subject Classification ID: 90C59
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 2117381
zbMATH Keywords: Approximation algorithms
zbMATH Keywords: Semidefinite programming
zbMATH Keywords: Maximum cut
describes a project that uses: Outward rotations
MaRDI profile type: Publication
full work available at URL: j.jcss.2003.07.012
OpenAlex ID: W4230348051
cites work: Interior Point Methods in Semidefinite Programming with Applications to Combinatorial Optimization
cites work: Q4517103
cites work: A new way of using semidefinite programming with applications to linear equations mod \(p\)
cites work: A Geometric Approach to Betweenness
cites work: On approximate graph colouring and MAX-\(k\)-CUT algorithms based on the \(\vartheta\)-function
cites work: Linear systems in Jordan algebras and primal-dual interior-point algorithms
cites work: Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
cites work: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
cites work: Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
cites work: The ellipsoid method and its consequences in combinatorial optimization
cites work: Geometric algorithms and combinatorial optimization
cites work: Barrier Functions in Interior Point Methods
cites work: Q4527033
cites work: Approximate graph coloring by semidefinite programming
cites work: Q3935355
cites work: Q4542562
cites work: On the Shannon capacity of a graph
cites work: Derandomizing Approximation Algorithms Based on Semidefinite Programming
cites work: Q4324980
cites work: Self-Scaled Barriers and Interior-Point Methods for Convex Programming
cites work: Primal-Dual Interior-Point Methods for Self-Scaled Cones
cites work: Convex quadratic and semidefinite programming relaxations in scheduling
cites work: The Chebyshev Polynomials of a Matrix
cites work: Q4250183
cites work: Outward rotations: a tool for rounding solutions of semidefinite programming relaxations, with applications to max cut and other problems
DOI: 10.1016/J.JCSS.2003.07.012
description: scientific article; zbMATH DE number 2117381