Minimum variance allocation among constrained intervals

Hsin Min Sun, Ruey Lin Sheu

Research output: Contribution to journalArticle

Abstract

We propose a weighted minimum variance allocation model, denoted by WMVA, which distributes an amount of a divisible resource as fairly as possible while satisfying all demand intervals. We show that the problem WMVA has a unique optimal solution and it can be characterized by the uniform distribution property (UDP in short). Based on the UDP property, we develop an efficient algorithm. Theoretically, our algorithm has a worst-case O(n 2 ) complexity, but we prove that, subject to slight conditions, the worst case cannot happen on a 64-bit computer when the problem dimension is greater than 129. We provide extensive simulation results to support the argument and it explains why, in practice, our algorithm runs significantly faster than most existing algorithms, including many O(n) algorithms.

Original languageEnglish
Pages (from-to)21-44
Number of pages24
JournalJournal of Global Optimization
Volume74
Issue number1
DOIs
Publication statusPublished - 2019 May 15

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Management Science and Operations Research
  • Control and Optimization
  • Applied Mathematics

Cite this