On approximate graph colouring and MAX-\(k\)-CUT algorithms based on the \(\vartheta\)-function

DOI10.1023/B:JOCO.0000038911.67280.3fzbMath1084.68142OpenAlexW2125240990WikidataQ56874382 ScholiaQ56874382MaRDI QIDQ1888168

Joost P. Warners, Dimitrii V. Pasechnik, Etienne de Klerk

Publication date: 22 November 2004

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/b:joco.0000038911.67280.3f

zbMATH Keywords

semidefinite programmingsatisfiabilityapproximation algorithmsGraph colouringMAX-\(k\)-CUTLovász \(\vartheta\)-function

Mathematics Subject Classification ID

Semidefinite programming (90C22) Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (27)

Matrix Relaxations in Combinatorial Optimization ⋮ Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming ⋮ Computational study of valid inequalities for the maximum \(k\)-cut problem ⋮ Semidefinite programming relaxations for graph coloring and maximal clique problems ⋮ SOME EXPERIENCES WITH SOLVING SEMIDEFINITE PROGRAMMING RELAXATIONS OF BINARY QUADRATIC OPTIMIZATION MODELS IN COMPUTATIONAL BIOLOGY ⋮ The Maximum k-Colorable Subgraph Problem and Related Problems ⋮ A class of spectral bounds for max \(k\)-cut ⋮ Unnamed Item ⋮ Computational study of a branching algorithm for the maximum \(k\)-cut problem ⋮ An approximation algorithm for maxk-uncut with capacity constraints ⋮ New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph ⋮ 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 branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem ⋮ The capacitated max \(k\)-cut problem ⋮ A branch-and-bound algorithm for solving max-\(k\)-cut problem ⋮ Optimal pricing in iterative flexible combinatorial procurement auctions ⋮ A semidefinite programming-based heuristic for graph coloring ⋮ Projection results for the \(k\)-partition problem ⋮ Maximally stable Gaussian partitions with discrete applications ⋮ Noise stability of functions with low influences: invariance and optimality ⋮ Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints ⋮ Semidefinite relaxations for partitioning, assignment and ordering problems ⋮ Computational Approaches to Max-Cut ⋮ Semidefinite relaxations for partitioning, assignment and ordering problems ⋮ Approximability Distance in the Space of H-Colourability Problems ⋮ Remarks on Gaussian Noise Stability, Brascamp-Lieb and Slepian Inequalities

This page was built for publication: On approximate graph colouring and MAX-\(k\)-CUT algorithms based on the \(\vartheta\)-function