Optimizing hypergraph-based polynomials modeling job-occupancy in queueing 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 (arXiv:2005.14566, 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
Number of pages39
JournalSIAM Journal on Optimization
Publication statusAccepted/In press - May 2021

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

Cite this