Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
From MaRDI portal
Publication:1887719
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
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
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
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
