Object Migration Automata for Non-equal Partitioning Problems with Known Partition Sizes

Autor: Lei Jiao, B. John Oommen, Rebekka Olsson Omslandseter
Přispěvatelé: University of Agder (UIA), Carleton University, Ilias Maglogiannis, John Macintyre, Lazaros Iliadis, TC 12, WG 12.5
Rok vydání: 2021
Předmět:
Zdroj: IFIP Advances in Information and Communication Technology ISBN: 9783030791490
AIAI
IFIP Advances in Information and Communication Technology
17th IFIP International Conference on Artificial Intelligence Applications and Innovations (AIAI)
17th IFIP International Conference on Artificial Intelligence Applications and Innovations (AIAI), Jun 2021, Hersonissos, Crete, Greece. pp.129-142, ⟨10.1007/978-3-030-79150-6_11⟩
DOI: 10.1007/978-3-030-79150-6_11
Popis: Part 4: Automated Machine Learning; International audience; Solving partitioning problems in random environments is a classic and challenging task, and has numerous applications. The existing Object Migration Automaton (OMA) and its proposed enhancements, which include the Pursuit and Transitivity phenomena, can solve problems with equi-sized partitions. Currently, these solutions also include one where the partition sizes possess a Greatest Common Divisor (GCD). In this paper, we propose an OMA-based solution that can solve problems with both equally and non-equally-sized groups, without restrictions on their sizes. More specifically, our proposed approach, referred to as the Partition Size Required OMA (PSR-OMA), can solve general partitioning problems, with the only additional requirement being that the unconstrained partitions’ sizes are known a priori. The scheme is a fundamental contribution in the field of partitioning algorithms, and the numerical results presented demonstrate that PSR-OMA can solve both equi-partitioning and non-equi-partitioning problems efficiently, and is the only known solution that resolves this problem.
Databáze: OpenAIRE
načítá se...