Semidefinite programming and its applications to NP problems

DOI10.1007/bfb0030878zbMath1527.68150MaRDI QIDQ6085755

Unnamed Author, Sanjeev Mahajan

Publication date: 12 December 2023

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Semidefinite programming (90C22) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• Unnamed Item
• Unnamed Item
• On the complexity of H-coloring
• On multiplicative graphs and the product conjecture
• The ellipsoid method and its consequences in combinatorial optimization
• Homomorphisms to oriented paths
• The sandwich theorem
• .879-approximation algorithms for MAX CUT and MAX 2SAT
• Approximate graph coloring by semidefinite programming
• A comparison of the Delsarte and Lovász bounds
• On the Shannon capacity of a graph
• Duality and Polynomial Testing of Tree Homomorphisms
• Monotone monadic SNP and constraint satisfaction

This page was built for publication: Semidefinite programming and its applications to NP problems