Recursive Balanced k-Subset Sum Partition for Rule-constrained Resource Allocation

Zhuo Li, Jiannong Cao, Zhongyu Yao, Wengen Li, Yu Yang, Jia Wang

Research output: Chapter in book / Conference proceedingConference article published in proceeding or bookAcademic researchpeer-review

1 Citation (Scopus)

Abstract

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.

Original languageEnglish
Title of host publicationCIKM 2020 - Proceedings of the 29th ACM International Conference on Information and Knowledge Management
PublisherAssociation for Computing Machinery
Pages2121-2124
Number of pages4
ISBN (Electronic)9781450368599
DOIs
Publication statusPublished - 19 Oct 2020
Event29th ACM International Conference on Information and Knowledge Management, CIKM 2020 - Virtual, Online, Ireland
Duration: 19 Oct 202023 Oct 2020

Publication series

NameInternational Conference on Information and Knowledge Management, Proceedings

Conference

Conference29th ACM International Conference on Information and Knowledge Management, CIKM 2020
Country/TerritoryIreland
CityVirtual, Online
Period19/10/2023/10/20

Keywords

  • balanced k-subset sum partition
  • rule-constrained resource allocation

ASJC Scopus subject areas

  • Business, Management and Accounting(all)
  • Decision Sciences(all)

Cite this