20220505
Symmetry reduction to optimize a graphbased polynomial from queueing theory
Publication
Publication
SIAM Journal on Applied Algebra and Geometry , Volume 6  Issue 2 p. 243 266
For given integers n and d, both at least 2, we consider a homogeneous multivariate polynomial fd of degree d in variables indexed by the edges of the complete graph on n vertices and coefficients depending on cardinalities of certain unions of edges. Cardinaels, Borst and van Leeuwaarden (arXiv:2111.05777, 2021) asked whether fd, which arises in a model of job occupancy in redundancy scheduling, attains its minimum over the standard simplex at the uniform probability vector. Brosch, Laurent, and Steenkamp [SIAM J. Optim. 31 (2021), 22272254] proved that fd is convex over the standard simplex if d = 2 and d = 3, implying the desired result for these d. We give a symmetry reduction to show that for fixed d, the polynomial is convex over the standard simplex (for all n \geq 2) if a constant number of constant matrices (with size and coefficients independent of n) are positive semidefinite. This result is then used in combination with a computerassisted verification to show that the polynomial fd is convex for d \leq 9.
Additional Metadata  

, , , , ,  
doi.org/10.1137/21M1413298  
SIAM Journal on Applied Algebra and Geometry  
Organisation  Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands 
Polak, S.C. (2022). Symmetry reduction to optimize a graphbased polynomial from queueing theory. SIAM Journal on Applied Algebra and Geometry, 6(2), 243–266. doi:10.1137/21M1413298
