Heuristic Algorithms for Balanced Multi-way Number Partitioning

Heuristic Algorithms for Balanced Multi-way Number Partitioning

Balanced multi-way number partitioning (BMNP) seeks to split a collection of numbers into subsets with (roughly) the same cardinality and subset sum. The problem is NP-hard, and there are several exact and approximate algorithms for it. However, existing exact algorithms solve only the simpler, bala...

Full description

Saved in:
Bibliographic Details
Main Authors: ZHANG, Jilian, MOURATIDIS, Kyriakos, PANG, Hwee Hwa
Format: text
Language:English
Published: Institutional Knowledge at Singapore Management University 2011
Subjects:
Approximate algorithms
Cardinalities
Exact algorithms
Heuristic techniques
Novel strategies
Number distribution
Number partitioning
Subset sum
Databases and Information Systems
Theory and Algorithms
Online Access:https://ink.library.smu.edu.sg/sis_research/1359
https://ink.library.smu.edu.sg/context/sis_research/article/2358/viewcontent/IJCAI11.pdf
Tags: Add Tag
No Tags, Be the first to tag this record!
Institution: Singapore Management University
Language: English
Description
Summary:Balanced multi-way number partitioning (BMNP) seeks to split a collection of numbers into subsets with (roughly) the same cardinality and subset sum. The problem is NP-hard, and there are several exact and approximate algorithms for it. However, existing exact algorithms solve only the simpler, balanced two-way number partitioning variant, whereas the most effective approximate algorithm, BLDM, may produce widely varying subset sums. In this paper, we introduce the LRM algorithm that lowers the expected spread in subset sums to one third that of BLDM for uniformly distributed numbers and odd subset cardinalities. We also propose Meld, a novel strategy for skewed number distributions. A combination of LRM and Meld leads to a heuristic technique that consistently achieves a narrower spread of subset sums than BLDM.

Similar Items