2021-09-07
Optimizing hypergraph-based polynomials modeling job-occupancy in queuing with redundancy scheduling
Publication
Publication
SIAM Journal on Optimization , Volume 31 - Issue 3 p. 2227- 2254
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.
| Additional Metadata | |
|---|---|
| , , , | |
| doi.org/10.1137/20M1369592 | |
| SIAM Journal on Optimization | |
| Mixed-Integer Nonlinear Optimization , Polynomial Optimization, Efficiency through Moments and Algebra | |
| , | |
| Organisation | CWI management |
|
Brosch, D., Laurent, M., & Steenkamp, A. (2021). Optimizing hypergraph-based polynomials modeling job-occupancy in queuing with redundancy scheduling. SIAM Journal on Optimization, 31(3), 2227–2254. doi:10.1137/20M1369592 |
|
