TY - GEN
T1 - Recursive Balanced k-Subset Sum Partition for Rule-constrained Resource Allocation
AU - Li, Zhuo
AU - Cao, Jiannong
AU - Yao, Zhongyu
AU - Li, Wengen
AU - Yang, Yu
AU - Wang, Jia
N1 - Funding Information:
This work was supported by Hong Kong Innovation and Technology Fund (ITF) (ITC No. ITP/024/18LP) and Guangdong Key Area R&D Plan (Project No. 2020B010164002).
Publisher Copyright:
© 2020 ACM.
Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2020/10/19
Y1 - 2020/10/19
N2 - Balanced rule-constrained resource allocation aims to evenly distribute tasks to different processors under allocation rule constraints. Conventional heuristic approach fails to achieve optimal solution while simple brute force method has the defect of high computational complexity. To address these limitations, we propose recursive balanced k-subset sum partition (RBkSP), in which iterative 'cut-one-out' policy is employed that in each round, only one subset whose weight of tasks sums up to 1/k of the total weight of all tasks is taken out from the set. In a single partition, we first create a dynamic programming table with its elements recursively computed, then use 'zig-zag search' method to explore the table, find out elements with optimal subset partition and assign different partitions to proper places. Next, to resolve conflicts during allocation, we use simple but effective heuristic method to adjust the allocation of tasks that is contradicted to allocation rules. Testing results show RBkSP can achieve more balanced results with lower computational complexity over classical benchmarks.
AB - Balanced rule-constrained resource allocation aims to evenly distribute tasks to different processors under allocation rule constraints. Conventional heuristic approach fails to achieve optimal solution while simple brute force method has the defect of high computational complexity. To address these limitations, we propose recursive balanced k-subset sum partition (RBkSP), in which iterative 'cut-one-out' policy is employed that in each round, only one subset whose weight of tasks sums up to 1/k of the total weight of all tasks is taken out from the set. In a single partition, we first create a dynamic programming table with its elements recursively computed, then use 'zig-zag search' method to explore the table, find out elements with optimal subset partition and assign different partitions to proper places. Next, to resolve conflicts during allocation, we use simple but effective heuristic method to adjust the allocation of tasks that is contradicted to allocation rules. Testing results show RBkSP can achieve more balanced results with lower computational complexity over classical benchmarks.
KW - balanced k-subset sum partition
KW - rule-constrained resource allocation
UR - http://www.scopus.com/inward/record.url?scp=85095862833&partnerID=8YFLogxK
U2 - 10.1145/3340531.3412076
DO - 10.1145/3340531.3412076
M3 - Conference article published in proceeding or book
AN - SCOPUS:85095862833
T3 - International Conference on Information and Knowledge Management, Proceedings
SP - 2121
EP - 2124
BT - CIKM 2020 - Proceedings of the 29th ACM International Conference on Information and Knowledge Management
PB - Association for Computing Machinery
T2 - 29th ACM International Conference on Information and Knowledge Management, CIKM 2020
Y2 - 19 October 2020 through 23 October 2020
ER -