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

Daniel Brosch, Monique Laurent*, Andries Steenkamp

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

Abstract

We investigate two classes of multivariate polynomials with variables indexed by the edges of a uniform hypergraph and coefficients depending on certain patterns of unions of edges. These polynomials arise naturally to model job-occupancy in some queuing problems with redundancy scheduling policies. The question, posed by Cardinaels, Borst, and van Leeuwaarden in [Redundancy Scheduling with Locally Stable Compatibility Graphs, arXiv preprint, 2020], is to decide whether their global minimum over the standard simplex is attained at the uniform probability distribution. By exploiting symmetry properties of these polynomials we can give a positive answer for the first class and partial results for the second one, where we in fact show a stronger convexity property of these polynomials over the simplex.

Original languageEnglish
Pages (from-to)2227-2254
JournalSIAM Journal on Optimization
Volume31
Issue number3
DOIs
Publication statusPublished - 7 Sep 2021

Keywords

  • Convex polynomial
  • Polynomial optimization
  • Symmetry
  • Terwilliger algebra

Fingerprint

Dive into the research topics of 'Optimizing hypergraph-based polynomials modeling job-occupancy in queuing with redundancy scheduling'. Together they form a unique fingerprint.

Cite this