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

Minimum Variance
Interval
Divisible
Uniform distribution
Efficient Algorithms
Optimal Solution
Resources
Minimum variance
Simulation
Model

All Science Journal Classification (ASJC) codes

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

Cite this

@article{66001f8edc9d49cc817f19c54c091f6c,
title = "Minimum variance allocation among constrained intervals",
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.",
author = "Sun, {Hsin Min} and Ruey-Lin Sheu",
year = "2019",
month = "5",
day = "15",
doi = "10.1007/s10898-019-00748-3",
language = "English",
volume = "74",
pages = "21--44",
journal = "Journal of Global Optimization",
issn = "0925-5001",
publisher = "Springer Netherlands",
number = "1",

}

Minimum variance allocation among constrained intervals. / Sun, Hsin Min; Sheu, Ruey-Lin.

In: Journal of Global Optimization, Vol. 74, No. 1, 15.05.2019, p. 21-44.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Minimum variance allocation among constrained intervals

AU - Sun, Hsin Min

AU - Sheu, Ruey-Lin

PY - 2019/5/15

Y1 - 2019/5/15

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85061326195&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85061326195&partnerID=8YFLogxK

U2 - 10.1007/s10898-019-00748-3

DO - 10.1007/s10898-019-00748-3

M3 - Article

VL - 74

SP - 21

EP - 44

JO - Journal of Global Optimization

JF - Journal of Global Optimization

SN - 0925-5001

IS - 1

ER -