5 papers
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…
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…
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…
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…
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…