# A 2-opt Algorithm for Locally Optimal Set Partition Optimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 54 references that are in the map.
- First posted on arXiv 14 Mar 2023.

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

- [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)
- [Nonparametric Extrema Analysis in Time Series for Envelope Extraction, Peak Detection and Clustering](https://mlsanity.com/paper/2109.02082/) (2021)
- [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)
- [Nonconvex Extension of Generalized Huber Loss for Robust Learning and Pseudo-Mode Statistics](https://mlsanity.com/paper/2202.11141/) (2022)
- [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)
- [A Linearithmic Time Locally Optimal Algorithm for the Multiway Number Partition Optimization](https://mlsanity.com/paper/2203.05618/) (2022)

## Abstract (arXiv)

Our research deals with the optimization version of the set partition problem, where the objective is to minimize the absolute difference between the sums of the two disjoint partitions. Although this problem is known to be NP-hard and requires exponential time to solve, we propose a less demanding version of this problem where the goal is to find a locally optimal solution. In our approach, we consider the local optimality in respect to any movement of at most two elements. To accomplish this, we developed an algorithm that can generate a locally optimal solution in at most O(N2) time and O(N) space. Our algorithm can handle arbitrary input precisions and does not require positive or integer inputs. Hence, it can be applied in various problem scenarios with ease.