Approximate graph coloring by semidefinite programming

DOI10.1145/274787.274791zbMath0904.68116MaRDI QIDQ3841651

Madhu Sudan, David R. Karger, Rajeev Motwani

Publication date: 11 January 1999

Published in: Journal of the ACM (Search for Journal in Brave)

Full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.56.413

zbMATH Keywords

semidefinite optimization problems

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

68W10: Parallel algorithms in computer science

Related Items

Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances, Interior point methods, a decade after Karmarkar—a survey, with application to the smallest eigenvalue problem, Graphs with Large Girth Not Embeddable in the Sphere, Communication Lower Bounds Via the Chromatic Number, Quadratic forms on graphs, On approximating the longest path in a graph, An improved algorithm for approximating the chromatic number of \(G_{n,p}\), Copositive programming motivated bounds on the stability and the chromatic numbers, Semidefinite programming relaxations for graph coloring and maximal clique problems, A simple algorithm for 4-coloring 3-colorable planar graphs, On the tractability of coloring semirandom graphs, Combinatorial optimization in system configuration design, Approximation algorithms for the weighted independent set problem in sparse graphs, Semidefinite programming in combinatorial optimization, Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function, Laplacian eigenvalues and fixed size multisection, Semidefinite programming, Heuristics for semirandom graph problems, Strengthening the Lovász \(\theta(\overline G)\) bound for graph coloring, Deciding \(k\)-colorability in expected polynomial time, Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming, The geometry of graphs and some of its algorithmic applications, Complexity of approximating bounded variants of optimization problems, On the adaptable chromatic number of graphs, A semidefinite programming-based heuristic for graph coloring, On the probabilistic minimum coloring and minimum \(k\)-coloring, Tales of Hoffman: three extensions of Hoffman's bound on the graph chromatic number, Semi-Definite positive Programming Relaxations for Graph K_n-Coloring in Frequency Assignment, Improved Approximation Guarantees through Higher Levels of SDP Hierarchies