1 citations · 1 across the 10 of their papers we have counts for
10 papers
On some k-fold generalizations of Lovász theta and their sandwich theorems
Marcel K Carli Silva, Gabriel Coutinho, Thiago Oliveira +1
We study several -fold generalizations of the Lovász theta function associated with the maximum -colorable induced subgraph problem. The first is the Narasimhan--Manber param…
Efficient Interior-Point Methods for Hyperbolic Programming via Straight-Line Programs
Mehdi Karimi, Levent Tuncel
Hyperbolic (HB) programming generalizes many popular convex optimization problems, including semidefinite and second-order cone programming. Despite substantial theoretical progres…
Normalizations of factorizations over convex cones and their effects on extension complexity
Adam Brown, Kanstantsin Pashkovich, Levent Tunçel
Factorizations over cones and their duals play central roles for many areas of mathematics and computer science. One of the reasons behind this is the ability to find a representat…
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…
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 ch…
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…
A Primal-Dual Extension of the Goemans--Williamson Algorithm for the Weighted Fractional Cut-Covering Problem
Nathan Benedetto Proença, Marcel K. de Carli Silva, Cristiane M. Sato +1
We study a weighted generalization of the fractional cut-covering problem, which we relate to the maximum cut problem via antiblocker and gauge duality. This relationship allows us…
Dyadic linear programming and extensions
Ahmad Abdi, Gérard Cornuéjols, Bertrand Guenin +1
A rational number is dyadic if it has a finite binary representation , where is an integer and is a nonnegative integer. Dyadic rationals are important for numerical…
On Connections Between Association Schemes and Analyses of Polyhedral and Positive Semidefinite Lift-and-Project Relaxations
Yu Hin Au, Nathan Lindzey, Levent Tunçel
We explore some connections between association schemes and the analyses of the semidefinite programming (SDP) based convex relaxations of combinatorial optimization problems in th…