4 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…