6533b85dfe1ef96bd12bf2ac
RESEARCH PRODUCT
Object Migration Automata for Non-equal Partitioning Problems with Known Partition Sizes
Lei JiaoB. John OommenRebekka Olsson Omslandsetersubject
Object partitioning with non-equal sizesScheme (programming language)Object Migration AutomataLearning automataComputer scienceLearning Automata0102 computer and information sciences01 natural sciencesPartition (database)Field (computer science)AutomatonTask (computing)010201 computation theory & mathematicsGreatest common divisorA priori and a posteriori[INFO]Computer Science [cs]computerAlgorithmComputer Science::Databasescomputer.programming_languagedescription
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.
year | journal | country | edition | language |
---|---|---|---|---|
2021-06-25 |