4 papers · 1 filter
On Rank-Monotone Graph Operations and Minimal Obstruction Graphs for the Lovász--Schrijver SDP Hierarchy
Yu Hin Au, Levent Tunçel
We study the lift-and-project rank of the stable set polytopes of graphs with respect to the Lovász--Schrijver SDP operator , with a particular focus on finding and c…
Efficient Implementation of Interior-Point Methods for Quantum Relative Entropy
Mehdi Karimi, Levent Tuncel
Quantum Relative Entropy (QRE) programming is a recently popular and challenging class of convex optimization problems with significant applications in quantum computing and quantu…
Everything is possible: constructing spectrahedra with prescribed facial dimensions
Vera Roshchina, Levent Tunçel
Given any finite set of nonnegative integers, there exists a closed convex set whose facial dimension signature coincides with this set of integers, that is, the dimensions of its…
Generalized Cuts and Grothendieck Covers: a Primal-Dual Approximation Framework Extending the Goemans--Williamson Algorithm
Nathan Benedetto Proença, Marcel K. de Carli Silva, Cristiane M. Sato +1
We provide a primal-dual framework for randomized approximation algorithms utilizing semidefinite programming (SDP) relaxations. Our framework pairs a continuum of APX-complete pro…