# A Quadratic Time Locally Optimal Algorithm for NP-hard Equal Cardinality Partition Optimization

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 54 references that are in the map.
- First posted on arXiv 16 Sep 2021.

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

- [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)
- [Fair Division Under Cardinality Constraints](https://mlsanity.com/paper/1804.09521/) (2018)
- [Optimal and Efficient Algorithms for General Mixable Losses against Switching Oracles](https://mlsanity.com/paper/2108.06411/) (2021)
- [Efficient Locally Optimal Number Set Partitioning for Scheduling, Allocation and Fair Selection](https://mlsanity.com/paper/2109.04809/) (2021)

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

- [A Linearithmic Time Locally Optimal Algorithm for the Multiway Number Partition Optimization](https://mlsanity.com/paper/2203.05618/) (2022)
- [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 optimization version of the equal cardinality set partition problem (where the absolute difference between the equal sized partitions' sums are minimized). While this problem is NP-hard and requires exponential complexity to solve in general, we have formulated a weaker version of this NP-hard problem, where the goal is to find a locally optimal solution. The local optimality considered in our work is under any swap between the opposing partitions' element pairs. To this end, we designed an algorithm which can produce such a locally optimal solution in O(N2) time and O(N) space. Our approach does not require positive or integer inputs and works equally well under arbitrary input precisions. Thus, it is widely applicable in different problem scenarios.