Approximate graph coloring by semidefinite programming
From MaRDI portal
Recommendations
Cited in
(only showing first 100 items - show all)- A class of semidefinite programs with rank-one solutions
- Constructing uniquely realizable graphs
- Quantum homomorphisms
- Computational study of a branching algorithm for the maximum \(k\)-cut problem
- Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
- Approximation algorithms for the weighted independent set problem in sparse graphs
- Improving the performance guarantee for approximate graph coloring
- Approximating the orthogonality dimension of graphs and hypergraphs
- Some experiences with solving semidefinite programming relaxations of binary quadratic optimization models in computational biology
- Semi-definite programming and quantum information
- New tools for graph coloring
- scientific article; zbMATH DE number 7561683 (Why is no real title available?)
- Improved Approximation Guarantees through Higher Levels of SDP Hierarchies
- More tales of Hoffman: bounds for the vector chromatic number of a graph
- Chromatic Gallai identities operating on Lovász number
- MAX k‐CUT and approximating the chromatic number of random graphs
- On the Lovász Theta Function for Independent Sets in Sparse Graphs
- Semidefinite programming
- On approximating the longest path in a graph
- Linearly ordered colourings of hypergraphs
- A notion of total dual integrality for convex, semidefinite, and extended formulations
- A simple algorithm for 4-coloring 3-colorable planar graphs
- On the tractability of coloring semirandom graphs
- Spectral lower bounds for the orthogonal and projective ranks of a graph
- An improved algorithm for approximating the chromatic number of \(G_{n,p}\)
- A semidefinite programming-based heuristic for graph coloring
- Cubical coloring -- fractional covering by cuts and semidefinite programming
- An SDP primal-dual algorithm for approximating the Lovász-theta function
- Graph homomorphisms via vector colorings
- Heuristics for semirandom graph problems
- Semi-definite positive programming relaxations for graph K_n-coloring in frequency assignment.
- Autour de nouvelles notions pour l'analyse des algorithmes d'approximation : de la structure de NPO à la structure des instances
- Coloring 3-colorable graphs with \(o(n^{1/5})\) colors
- Quadratic forms on graphs
- Interior point methods, a decade after Karmarkar—a survey, with application to the smallest eigenvalue problem
- An approximate algorithm for the (k,d)-coloring problem
- An \(\tilde{O}(n^{3/14})\)-coloring algorithm for 3-colorable graphs
- Computing the partition function for graph homomorphisms
- Graphs with Large Girth Not Embeddable in the Sphere
- Hypercontractive inequalities via SOS, and the Frankl-Rödl graph
- New spectral bounds on the chromatic number encompassing all eigenvalues of the adjacency matrix
- Approximation Algorithms for Semidefinite Packing Problems with Applications to Maxcut and Graph Coloring
- The approximability of assortment optimization under ranking preferences
- Matrix relaxations in combinatorial optimization
- scientific article; zbMATH DE number 4091188 (Why is no real title available?)
- Linear index coding via semidefinite programming
- New semidefinite programming relaxations for the linear ordering and the traveling salesman problem
- Computational approaches to MAX-cut
- Semidefinite programming in combinatorial optimization
- New heuristics for the vertex coloring problem based on semidefinite programming
- Grothendieck-type inequalities in combinatorial optimization
- Computing Semidefinite Programming Lower Bounds for the (Fractional) Chromatic Number Via Block-Diagonalization
- The Lovász theta function for random regular graphs and community detection in the hard regime
- The geometry of graphs and some of its algorithmic applications
- Finding Pseudorandom Colorings of Pseudorandom Graphs
- scientific article; zbMATH DE number 7650095 (Why is no real title available?)
- The Lovász number of random graphs
- Copositive programming motivated bounds on the stability and the chromatic numbers
- Solving graph coloring problems with the Douglas-Rachford algorithm
- Regular inference as vertex coloring
- Balanced coloring of bipartite graphs
- Graph coloring and semidefinite rank
- Laplacian eigenvalues and fixed size multisection
- Wireless capacity with arbitrary gain matrix
- Semidefinite programming relaxations for graph coloring and maximal clique problems
- Approximation Algorithms for CSPs
- scientific article; zbMATH DE number 2119717 (Why is no real title available?)
- Shannon capacity and the categorical product
- Improving the linear relaxation of maximum \(k\)-cut with semidefinite-based constraints
- Tales of Hoffman: three extensions of Hoffman's bound on the graph chromatic number
- Spectral bounds for the independence ratio and the chromatic number of an operator
- Complexity of approximating bounded variants of optimization problems
- Combinatorial optimization in system configuration design
- Generating cutting planes for the semidefinite relaxation of quadratic programs
- Robust Factorizations and Colorings of Tensor Graphs
- An enhanced formulation for solving graph coloring problems with the Douglas-Rachford algorithm
- Strengthening the Lovász \(\theta(\overline G)\) bound for graph coloring
- Graph coloring and semidefinite rank
- Total coloring and total matching: polyhedra and facets
- A unified construction of semiring-homomorphic graph invariants
- Cone-LP's and semidefinite programs: geometry and a simplex-type method
- The entropy rounding method in approximation algorithms
- Sabidussi versus Hedetniemi for three variations of the chromatic number
- Sampling Strategies for Fast Updating of Gaussian Markov Random Fields
- On approximability of satisfiable k-CSPs: V
- The core of a complementary prism
- A primal-dual extension of the Goemans-Williamson algorithm for the weighted fractional cut-covering problem
- Communication Lower Bounds Via the Chromatic Number
- Orthonormal representations, vector chromatic number, and extension complexity
- Hardness of coloring 2-colorable 12-uniform hypergraphs with \(2^{(\log n)^{\Omega(1)}}\) colors
- Moment inequalities for sums of random matrices and their applications in optimization
- scientific article; zbMATH DE number 2086377 (Why is no real title available?)
- Hoffman colorability of (strongly) regular graphs
- Semidefinite programming and its applications to NP problems
- Spectral lower bounds for the quantum chromatic number of a graph
- Graph coloring in the estimation of sparse derivative matrices: Instances and applications
- scientific article; zbMATH DE number 7626745 (Why is no real title available?)
- Vertex cover in graphs with locally few colors
- Coloring tournaments with few colors: algorithms and complexity
- An efficient semidefinite programming relaxation for the graph partition problem
This page was built for publication: Approximate graph coloring by semidefinite programming
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3841651)
