Abstract
In the resource allocation problem (RAP), the goal is to divide a given amount of resource over a set of activities while minimizing the cost of this allocation and possibly satisfying constraints on allocations to subsets of the activities. Most solution approaches for the RAP and its extensions allow each activity to have its own cost function. However, in many applications, often the structure of the objective function is the same for each activity and the difference between the cost functions lies in different parameter choices such as, e.g., the multiplicative factors. In this article, we introduce a new class of objective functions that captures the majority of the objectives occurring in studied applications. These objectives are characterized by a shared structure of the cost function depending on two input parameters. We show that, given the two input parameters, there exists a solution to the RAP that is optimal for any choice of the shared structure. As a consequence, this problem reduces to the quadratic RAP, making available the vast amount of solution approaches and algorithms for the latter problem. We show the impact of our reduction result on several applications and, in particular, we improve the best known worst-case complexity bound of two important problems in vessel routing and processor scheduling from $O(n^2)$ to $O(n \log n)$.
Original language | English |
---|---|
Publisher | ArXiv.org |
Number of pages | 24 |
DOIs | |
Publication status | Published - 26 Aug 2020 |
Keywords
- math.OC
Fingerprint
Dive into the research topics of 'On a reduction for a class of resource allocation problems'. Together they form a unique fingerprint.
View full fingerprint
- 1 Article
-
On a Reduction for a Class of Resource Allocation Problems
Uiterkamp, M. H. H. S., Gerards, M. E. T. & Hurink, J. L., May 2022, In: INFORMS journal on computing. 34, 3, p. 1387-1402 16 p.
Research output: Contribution to journal › Article › Academic › peer-review
Open Access
File
5 Citations(Scopus)
51 Downloads(Pure)
Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver
Uiterkamp, M. H. H. S., Gerards, M. E. T. (2020). On a reduction for a class of resource allocation problems. ArXiv.org. https://doi.org/10.48550/arXiv.2008.11829
Uiterkamp, Martijn H.H. Schoot ; Gerards, Marco E.T. ; Hurink, Johann L. / On a reduction for a class of resource allocation problems. ArXiv.org, 2020.
@techreport{51ed960fb4cf4ed196165ff1ac5d524a,
title = "On a reduction for a class of resource allocation problems",
abstract = " In the resource allocation problem (RAP), the goal is to divide a given amount of resource over a set of activities while minimizing the cost of this allocation and possibly satisfying constraints on allocations to subsets of the activities. Most solution approaches for the RAP and its extensions allow each activity to have its own cost function. However, in many applications, often the structure of the objective function is the same for each activity and the difference between the cost functions lies in different parameter choices such as, e.g., the multiplicative factors. In this article, we introduce a new class of objective functions that captures the majority of the objectives occurring in studied applications. These objectives are characterized by a shared structure of the cost function depending on two input parameters. We show that, given the two input parameters, there exists a solution to the RAP that is optimal for any choice of the shared structure. As a consequence, this problem reduces to the quadratic RAP, making available the vast amount of solution approaches and algorithms for the latter problem. We show the impact of our reduction result on several applications and, in particular, we improve the best known worst-case complexity bound of two important problems in vessel routing and processor scheduling from $O(n^2)$ to $O(n \log n)$. ",
keywords = "math.OC",
author = "Uiterkamp, {Martijn H.H. Schoot} and Gerards, {Marco E.T.} and Hurink, {Johann L.}",
year = "2020",
month = aug,
day = "26",
doi = "10.48550/arXiv.2008.11829",
language = "English",
publisher = "ArXiv.org",
type = "WorkingPaper",
institution = "ArXiv.org",
}
Uiterkamp, MHHS, Gerards, MET 2020 'On a reduction for a class of resource allocation problems' ArXiv.org. https://doi.org/10.48550/arXiv.2008.11829
On a reduction for a class of resource allocation problems. / Uiterkamp, Martijn H.H. Schoot; Gerards, Marco E.T.; Hurink, Johann L.
ArXiv.org, 2020.
Research output: Working paper › Preprint › Academic
TY - UNPB
T1 - On a reduction for a class of resource allocation problems
AU - Uiterkamp, Martijn H.H. Schoot
AU - Gerards, Marco E.T.
AU - Hurink, Johann L.
PY - 2020/8/26
Y1 - 2020/8/26
N2 - In the resource allocation problem (RAP), the goal is to divide a given amount of resource over a set of activities while minimizing the cost of this allocation and possibly satisfying constraints on allocations to subsets of the activities. Most solution approaches for the RAP and its extensions allow each activity to have its own cost function. However, in many applications, often the structure of the objective function is the same for each activity and the difference between the cost functions lies in different parameter choices such as, e.g., the multiplicative factors. In this article, we introduce a new class of objective functions that captures the majority of the objectives occurring in studied applications. These objectives are characterized by a shared structure of the cost function depending on two input parameters. We show that, given the two input parameters, there exists a solution to the RAP that is optimal for any choice of the shared structure. As a consequence, this problem reduces to the quadratic RAP, making available the vast amount of solution approaches and algorithms for the latter problem. We show the impact of our reduction result on several applications and, in particular, we improve the best known worst-case complexity bound of two important problems in vessel routing and processor scheduling from $O(n^2)$ to $O(n \log n)$.
AB - In the resource allocation problem (RAP), the goal is to divide a given amount of resource over a set of activities while minimizing the cost of this allocation and possibly satisfying constraints on allocations to subsets of the activities. Most solution approaches for the RAP and its extensions allow each activity to have its own cost function. However, in many applications, often the structure of the objective function is the same for each activity and the difference between the cost functions lies in different parameter choices such as, e.g., the multiplicative factors. In this article, we introduce a new class of objective functions that captures the majority of the objectives occurring in studied applications. These objectives are characterized by a shared structure of the cost function depending on two input parameters. We show that, given the two input parameters, there exists a solution to the RAP that is optimal for any choice of the shared structure. As a consequence, this problem reduces to the quadratic RAP, making available the vast amount of solution approaches and algorithms for the latter problem. We show the impact of our reduction result on several applications and, in particular, we improve the best known worst-case complexity bound of two important problems in vessel routing and processor scheduling from $O(n^2)$ to $O(n \log n)$.
KW - math.OC
U2 - 10.48550/arXiv.2008.11829
DO - 10.48550/arXiv.2008.11829
M3 - Preprint
BT - On a reduction for a class of resource allocation problems
PB - ArXiv.org
ER -
Uiterkamp MHHS, Gerards MET, Hurink JL. On a reduction for a class of resource allocation problems. ArXiv.org. 2020 Aug 26. doi: 10.48550/arXiv.2008.11829