4 papers · 1 filter
Optimal Cuts and Optimal Faces of Exact Max-Cut Semidefinite Relaxations
Avinash Bhardwaj, Chen Chen, Vishnu Narayanan
An exact Max-Cut semidefinite relaxation can have optima outside the convex hull of optimal cut matrices. We study when this hull equals the optimal face and how to recognize equal…
Max--Cut via Node Features
Avinash Bhardwaj, Hritiz Gogoi, Vishnu Narayanan
We study the Max--Cut problem from a node-feature perspective, where each vertex is associated with a feature vector and edge weights are given by pairwise inner products. We fi…
On exactness of SDP relaxation for the maximum cut problem
Avinash Bhardwaj, Hritiz Gogoi, Vishnu Narayanan +1
Semidefinite programming (SDP) provides a powerful relaxation for the maximum cut problem. In this work, we characterize a few classes of graphs for which the SDP relaxation is exa…
On generators of -PSD closures of the positive semidefinite cone
Avinash Bhardwaj, Vishnu Narayanan, Abhishek Pathapati
Positive semidefinite (PSD) cone is the cone of positive semidefinite matrices, and is the object of interest in semidefinite programming (SDP). A computational efficient approxima…