Approximate graph coloring by semidefinite programming
From MaRDI portal
Publication:3841651
DOI10.1145/274787.274791zbMath0904.68116OpenAlexW2069816168MaRDI 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
Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10)
Related Items
Grothendieck-Type Inequalities in Combinatorial Optimization, An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs, Complexity of approximating bounded variants of optimization problems, Matrix Relaxations in Combinatorial Optimization, Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming, Sampling Strategies for Fast Updating of Gaussian Markov Random Fields, An improved algorithm for approximating the chromatic number of \(G_{n,p}\), The geometry of graphs and some of its algorithmic applications, Copositive programming motivated bounds on the stability and the chromatic numbers, Generating cutting planes for the semidefinite relaxation of quadratic programs, Semidefinite programming in combinatorial optimization, New heuristics for the vertex coloring problem based on semidefinite programming, Graph coloring and semidefinite rank, Semidefinite programming relaxations for graph coloring and maximal clique problems, Shannon capacity and the categorical product, SOME EXPERIENCES WITH SOLVING SEMIDEFINITE PROGRAMMING RELAXATIONS OF BINARY QUADRATIC OPTIMIZATION MODELS IN COMPUTATIONAL BIOLOGY, Randomized graph products, chromatic numbers, and the Lovász \(\vartheta\)-function, On the Lovász Theta Function for Independent Sets in Sparse Graphs, An enhanced formulation for solving graph coloring problems with the Douglas-Rachford algorithm, Universal completability, least eigenvalue frameworks, and vector colorings, Sabidussi versus Hedetniemi for three variations of the chromatic number, Computational study of a branching algorithm for the maximum \(k\)-cut problem, Constructing uniquely realizable graphs, Total coloring and total matching: polyhedra and facets, New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix, The core of a complementary prism, Semidefinite programming and its applications to NP problems, Graph homomorphisms via vector colorings, Vector coloring the categorical product of graphs, Solving graph equipartition SDPs on an algebraic variety, Unnamed Item, On the adaptable chromatic number of graphs, Unnamed Item, Robust Factorizations and Colorings of Tensor Graphs, An Efficient Semidefinite Programming Relaxation for the Graph Partition Problem, Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes, Hardness of Coloring 2-Colorable 12-Uniform Hypergraphs with $2^{(\log {n})^{\Omega(1)}}$ Colors, Unnamed Item, Moment inequalities for sums of random matrices and their applications in optimization, Laplacian eigenvalues and fixed size multisection, The Approximability of Assortment Optimization Under Ranking Preferences, Regular inference as vertex coloring, Spectral bounds for the independence ratio and the chromatic number of an operator, Homomorphisms of strongly regular graphs, Improved Approximation Guarantees through Higher Levels of SDP Hierarchies, Chromatic Gallai identities operating on Lovász number, Approximation Algorithms for CSPs, Coloring the normalized Laplacian for oriented hypergraphs, Quadratic forms on graphs, Price of anarchy for graph coloring games with concave payoff, A semidefinite programming-based heuristic for graph coloring, Vertex Cover in Graphs with Locally Few Colors, On approximating the longest path in a graph, Cone-LP's and semidefinite programs: Geometry and a simplex-type method, Coloring bipartite hypergraphs, Unnamed Item, Computing the partition function for graph homomorphisms, An axiomatic duality framework for the theta body and related convex corners, Linear Index Coding via Semidefinite Programming, An SDP primal-dual algorithm for approximating the Lovász-theta function, On the probabilistic minimum coloring and minimum \(k\)-coloring, A class of semidefinite programs with rank-one solutions, A simple algorithm for 4-coloring 3-colorable planar graphs, Graphs with Large Girth Not Embeddable in the Sphere, Semi-Definite positive Programming Relaxations for Graph Kn-Coloring in Frequency Assignment, On the tractability of coloring semirandom graphs, Strengthening the Lovász \(\theta(\overline G)\) bound for graph coloring, Tales of Hoffman: three extensions of Hoffman's bound on the graph chromatic number, Balanced coloring of bipartite graphs, Unnamed Item, New semidefinite programming relaxations for the linear ordering and the traveling salesman problem, Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints, Convex Relaxations and Integrality Gaps, Computational Approaches to Max-Cut, Communication Lower Bounds Via the Chromatic Number, Wireless capacity with arbitrary gain matrix, A Notion of Total Dual Integrality for Convex, Semidefinite, and Extended Formulations, A unified construction of semiring-homomorphic graph invariants, New Tools for Graph Coloring, Interior point methods, a decade after Karmarkar—a survey, with application to the smallest eigenvalue problem, Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances, Hypercontractive inequalities via SOS, and the Frankl--Rödl graph, On fractional cut covers, Combinatorial optimization in system configuration design, Approximation algorithms for the weighted independent set problem in sparse graphs, The Lovász Theta Function for Random Regular Graphs and Community Detection in the Hard Regime, Spectral lower bounds for the orthogonal and projective ranks of a graph, Spectral lower bounds for the quantum chromatic number of a graph, Deciding \(k\)-colorability in expected polynomial time, Unnamed Item, Unnamed Item, Unnamed Item, Semidefinite programming, More tales of Hoffman: bounds for the vector chromatic number of a graph, Hardness of Rainbow Coloring Hypergraphs, Heuristics for semirandom graph problems, Finding Pseudorandom Colorings of Pseudorandom Graphs, Quantum homomorphisms
