Optimizing hypergraph-based polynomials modeling job-occupancy in queueing with redundancy scheduling

We investigate two classes of multivariate polynomials with variables indexed by the edges of a uniform hypergraph and coefficients depending on certain patterns of union of edges. These polynomials arise naturally to model job-occupancy in some queuing problems with redundancy scheduling policy. The question, posed by Cardinaels, Borstand van Leeuwaarden (arXiv:2005.14566, 2020), is to decide … Read more

Symmetry in semidefinite programs

This paper is a tutorial in a general and explicit procedure to simplify semidefinite programming problems which are invariant under the action of a group. The procedure is based on basic notions of representation theory of finite groups. As an example we derive the block diagonalization of the Terwilliger algebra in this framework. Here its … Read more

Computing semidefinite programming lower bounds for the (fractional) chromatic number via block-diagonalization

Recently we investigated in “The operator $\Psi$ for the Chromatic Number of a Graph” hierarchies of semidefinite approximations for the chromatic number $\chi(G)$ of a graph $G$. In particular, we introduced two hierarchies of lower bounds, the `$\psi$’-hierarchy converging to the fractional chromatic number, and the `$\Psi$’-hierarchy converging to the chromatic number of a graph. … Read more

Approximating the Chromatic Number of a Graph by Semidefinite Programming

We investigate hierarchies of semidefinite approximations for the chromatic number $\chi(G)$ of a graph $G$. We introduce an operator $\Psi$ mapping any graph parameter $\beta(G)$, nested between the stability number $\alpha(G)$ and $\chi(\bar G)$, to a new graph parameter $\Psi_\beta(G)$, nested between $\omega(G)$ and $\chi(G)$; $\Psi_\beta(G)$ is polynomial time computable if $\beta(G)$ is. As an … Read more