资源论文Heuristic Algorithms for Balanced Multi-Way Number Partitioning Jilian Zhang Kyriakos Mouratidis HweeHwa Pang

Heuristic Algorithms for Balanced Multi-Way Number Partitioning Jilian Zhang Kyriakos Mouratidis HweeHwa Pang

2019-11-12 | |  32 |   43 |   0
Abstract 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.

上一篇:Symmetry Breaking via LexLeader Feasibility Checkers

下一篇:What Is an Ideal Logic for Reasoning with Inconsistency? Ofer Arieli Arnon Avron Anna Zamansky

用户评价
全部评价

热门资源

  • Learning to Predi...

    Much of model-based reinforcement learning invo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • The Variational S...

    Unlike traditional images which do not offer in...

  • Learning to learn...

    The move from hand-designed features to learned...

  • A Mathematical Mo...

    Direct democracy, where each voter casts one vo...