Zobrazeno 1 - 10
of 24
pro vyhledávání: '"Silva, Marcel K. de Carli"'
We provide a primal-dual framework for randomized approximation algorithms utilizing semidefinite programming (SDP) relaxations. Our framework pairs a continuum of APX-complete problems including MaxCut, Max2Sat, MaxDicut, and more generally, Max-Boo
Externí odkaz:
http://arxiv.org/abs/2406.18670
We show that Hoffman's sum of eigenvalues bound for the chromatic number is at least as good as the Lov\'asz theta number, but no better than the ceiling of the fractional chromatic number. In order to do so, we display an interesting connection betw
Externí odkaz:
http://arxiv.org/abs/2106.11121
Publikováno v:
Electronic Notes in Theoretical Computer Science, 346, 275 - 283 (2019)
We extend the clique-coclique inequality, previously known to hold for graphs in association schemes and vertex-transitive graphs, to graphs in homogeneous coherent configurations and 1-walk regular graphs. We further generalize it to a stronger ineq
Externí odkaz:
http://arxiv.org/abs/1910.06260
The notion of duality is a key element in understanding the interplay between the stability and chromatic numbers of a graph. This notion is a central aspect in the celebrated theory of perfect graphs, and is further and deeply developed in the conte
Externí odkaz:
http://arxiv.org/abs/1910.05586
The MaxCut SDP is one of the most well-known semidefinite programs, and it has many favorable properties. One of its nicest geometric/duality properties is the fact that the vertices of its feasible region correspond exactly to the cuts of a graph, a
Externí odkaz:
http://arxiv.org/abs/1806.01173
We prove that every pointed closed convex set in $\mathbb{R}^n$ is the intersection of all the rational closed halfspaces that contain it. This generalizes a previous result by the authors for compact convex sets.
Externí odkaz:
http://arxiv.org/abs/1802.03296
Total dual integrality is a powerful and unifying concept in polyhedral combinatorics and integer programming that enables the refinement of geometric min-max relations given by linear programming Strong Duality into combinatorial min-max theorems. T
Externí odkaz:
http://arxiv.org/abs/1801.09155
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. It makes it possible to derive bounds for parameters in extremal combin
Externí odkaz:
http://arxiv.org/abs/1607.04741
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 theory, and semidefinite optimization. In this paper, utilizing a mod
Externí odkaz:
http://arxiv.org/abs/1412.2103
Utilizing dual descriptions of the normal cone of convex optimization problems in conic form, we characterize the vertices of semidefinite representations arising from Lov\'asz theta body, generalizations of the elliptope, and related convex sets. Ou
Externí odkaz:
http://arxiv.org/abs/1309.7415