# A Linearithmic Time Locally Optimal Algorithm for the Multiway Number Partition Optimization

arXiv: https://arxiv.org/abs/2203.05618 · HTML: https://mlsanity.com/paper/2203.05618/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 79 references that are in the map.
- First posted on arXiv 10 Mar 2022.

## Builds on (most cited first, 9 of 9)

- [Generalized Huber Loss for Robust Learning and its Efficient Minimization for a Robust Statistics](https://mlsanity.com/paper/2108.12627/) (2021)
- [Optimally Efficient Sequential Calibration of Binary Classifiers to Minimize Classification Error](https://mlsanity.com/paper/2108.08780/) (2021)
- [Recursive Experts: An Efficient Optimal Mixture of Learning Systems in Dynamic Environments](https://mlsanity.com/paper/2009.09249/) (2020)
- [Fair Division Under Cardinality Constraints](https://mlsanity.com/paper/1804.09521/) (2018)
- [Low Regret Binary Sampling Method for Efficient Global Optimization of Univariate Functions](https://mlsanity.com/paper/2201.07164/) (2022)
- [Optimal and Efficient Algorithms for General Mixable Losses against Switching Oracles](https://mlsanity.com/paper/2108.06411/) (2021)
- [Cumulative Regret Analysis of the Piyavskii--Shubert Algorithm and Its Variants for Global Optimization](https://mlsanity.com/paper/2108.10859/) (2021)
- [Efficient Locally Optimal Number Set Partitioning for Scheduling, Allocation and Fair Selection](https://mlsanity.com/paper/2109.04809/) (2021)
- [A Quadratic Time Locally Optimal Algorithm for NP-hard Equal Cardinality Partition Optimization](https://mlsanity.com/paper/2109.07882/) (2021)

## Built on by (most cited first, 2 of 2)

- [Merging Knockout and Round-Robin Tournaments: A Flexible Linear Elimination Tournament Design](https://mlsanity.com/paper/2203.12011/) (2022)
- [A 2-opt Algorithm for Locally Optimal Set Partition Optimization](https://mlsanity.com/paper/2303.08219/) (2023)

## Abstract (arXiv)

We study the problem of multiway number partition optimization, which has a myriad of applications in the decision, learning and optimization literature. Even though the original multiway partitioning problem is NP-hard and requires exponential time complexity algorithms; we formulate an easier optimization problem, where our goal is to find a solution that is locally optimal. We propose a linearithmic time complexity O(Nlog N) algorithm that can produce such a locally optimal solution. Our method is robust against the input and requires neither positive nor integer inputs.