scientific article; zbMATH DE number 1256751

MaRDI QIDQ4228487zbMATH OpenFDO

Authors Hsueh-I Lu, Philip N. Klein

Publication date 28 May 2000

zbMATH Keywords

graph coloringgraph MAX CUT

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Approximation Algorithms for Semidefinite Packing Problems with Applications to Maxcut and Graph Coloring
• Approximate graph coloring by semidefinite programming
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• On approximate graph colouring and MAX-k-CUT algorithms based on the -function

Cited in

(23)

• On approximate graph colouring and MAX-k-CUT algorithms based on the -function
• Semidefinite programming and approximation algorithms: a survey
• MAX k‐CUT and approximating the chromatic number of random graphs
• Cubical coloring -- fractional covering by cuts and semidefinite programming
• An SDP primal-dual algorithm for approximating the Lovász-theta function
• Approximating spectral sums of large-scale matrices using stochastic Chebyshev approximations
• An experimental evaluation of semidefinite programming and spectral algorithms for max cut
• Constructing worst case instances for semidefinite programming based approximation algorithms
• Approximation Algorithms for Semidefinite Packing Problems with Applications to Maxcut and Graph Coloring
• Finding Sparse Solutions for Packing and Covering Semidefinite Programs
• A combinatorial, primal-dual approach to semidefinite programs
• Approximating sparse quadratic programs
• Semidefinite programming relaxations for graph coloring and maximal clique problems
• Graph coloring and semidefinite rank
• Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming
• Approximate graph coloring by semidefinite programming
• The multiplicative weights update method: a meta-algorithm and applications
• Approximating maximum stable set and minimum graph coloring problems with the positive semidefinite relaxation
• Batched Stochastic Gradient Descent with Weighted Sampling
• Convergence rate of block-coordinate maximization Burer-Monteiro method for solving large SDPs
• Memory-efficient structured convex optimization via extreme point sampling
• Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs
• An efficiently computable subgraph pattern support measure: counting independent observations

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4228487)