scientific article; zbMATH DE number 1256751

zbMATH Open0936.68072MaRDI QIDQ4228487FDOQ4228487

Authors: Hsueh-I Lu, Philip N. Klein 

Publication date: 28 May 2000

Title of this publication is not available (Why is that?)

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 \(\vartheta\)-function

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)

Cited In (23)

• On approximate graph colouring and MAX-\(k\)-CUT algorithms based on the \(\vartheta\)-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
• Batched Stochastic Gradient Descent with Weighted Sampling
• Approximating maximum stable set and minimum graph coloring problems with the positive semidefinite relaxation
• Memory-efficient structured convex optimization via extreme point sampling
• Oracle-Based Primal-Dual Algorithms for Packing and Covering Semidefinite Programs
• Convergence rate of block-coordinate maximization Burer-Monteiro method for solving large SDPs
• 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)