7 citations · 13 across the 11 of their papers we have counts for
4 papers · 2 filters
Rank-sensitive vertex bounds for semidefinite lifts
Avinash Bhardwaj
We study how the ranks of factors in a positive semidefinite slack factorization constrain its size. We bound the number of low-rank vertex factors in any fixed factorization, and…
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…
The Complexity of Recognizing SDP Exactness for the Maximum Cut Problem
Avinash Bhardwaj
The standard semidefinite programming (SDP) relaxation of Max-Cut is exact when its optimum equals the maximum cut value. Delorme and Poljak resolved NP-completeness of recognizing…
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…