Semidefinite programming and its applications to NP problems

DOI10.1007/BFB0030878MaRDI QIDQ6085755zbMATH OpenFDO

Authors Sanjeev Mahajan

Publication date 12 December 2023

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

Full work available at URL https://doi.org/10.1007/BFB0030878

Mathematics Subject Classification ID

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

Recommendations

• A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for Some NP-Hard Graph Optimization Problems
• Relaxations of the satisfiability problem using semidefinite programming
• Relaxations of the satisfiability problem using semidefinite programming
• Semidefinite programming in combinatorial and polynomial optimization
• Lower bounds on the size of semidefinite programming relaxations

Cites work

• .878-approximation algorithms for MAX CUT and MAX 2SAT
• A comparison of the Delsarte and Lovász bounds
• Approximate graph coloring by semidefinite programming
• Duality and Polynomial Testing of Tree Homomorphisms
• Homomorphisms to oriented paths
• scientific article; zbMATH DE number 3854804 (Why is no real title available?)
• scientific article; zbMATH DE number 878894 (Why is no real title available?)
• Monotone monadic SNP and constraint satisfaction
• On multiplicative graphs and the product conjecture
• On the complexity of H-coloring
• On the Shannon capacity of a graph
• The ellipsoid method and its consequences in combinatorial optimization
• The sandwich theorem

Cited in

(8)

• On the complexity of semidefinite programs
• \(\mathcal{UV}\)-theory of a class of semidefinite programming and its applications
• MPF problem over modified medial semigroup is NP-complete
• scientific article; zbMATH DE number 6000615 (Why is no real title available?)
• scientific article; zbMATH DE number 4001882 (Why is no real title available?)
• scientific article; zbMATH DE number 2081093 (Why is no real title available?)
• scientific article; zbMATH DE number 1489798 (Why is no real title available?)
• SDPA PROJECT : SOLVING LARGE-SCALE SEMIDEFINITE PROGRAMS(<Special Issue>the 50th Anniversary of the Operations Research Society of Japan)

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

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