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

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