3 citations · 7 across the 7 of their papers we have counts for
7 papers
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…
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…
An eigenvalue bound for the fractional chromatic number
Marcel K. de Carli Silva, Gabriel Coutinho, Rafael Grandsire
We show that Hoffman's sum of eigenvalues bound for the chromatic number is at least as good as the Lovász theta number, but no better than the ceiling of the fractional chromatic…
Flag Algebras: A First Glance
Marcel K. de Carli Silva, Fernando Mário de Oliveira Filho, Cristiane Maria Sato
The theory of flag algebras, introduced by Razborov in 2007, has opened the way to a systematic approach to the development of computer-assisted proofs in extremal combinatorics. I…
An Axiomatic Duality Framework for the Theta Body and Related Convex Corners
Marcel K. de Carli Silva, Levent Tunçel
Lovasz theta function and the related theta body of graphs have been in the center of the intersection of four research areas: combinatorial optimization, graph theory, information…
Vertices of Spectrahedra arising from the Elliptope, the Theta Body, and Their Relatives
Marcel K. de Carli Silva, Levent Tunçel
Utilizing dual descriptions of the normal cone of convex optimization problems in conic form, we characterize the vertices of semidefinite representations arising from Lovász theta…
Optimization Problems over Unit-Distance Representations of Graphs
Marcel K. de Carli Silva, Levent Tunçel
We study the relationship between unit-distance representations and Lovasz theta number of graphs, originally established by Lovasz. We derive and prove min-max theorems. This fram…