mlsanityData to 13 Oct 2026

A 2-opt Algorithm for Locally Optimal Set Partition Optimization

arXiv 2303.08219 ↗First posted 14 Mar 2023cs.DS cs.LG math.COcited by 0

Not on the map. Why?

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.

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

Builds on

10 of 54 references.

References · 10

  1. 2021Optimally Efficient Sequential Calibration of Binary Classifiers to Minimize Classification Errorcited by 17
  2. 2020Recursive Experts: An Efficient Optimal Mixture of Learning Systems in Dynamic Environmentscited by 15
  3. 2021Nonparametric Extrema Analysis in Time Series for Envelope Extraction, Peak Detection and Clusteringcited by 12
  4. 2022Low Regret Binary Sampling Method for Efficient Global Optimization of Univariate Functionscited by 11
  5. 2018Fair Division Under Cardinality Constraintscited by 10
  6. 2021Optimal and Efficient Algorithms for General Mixable Losses against Switching Oraclescited by 10
  7. 2022Nonconvex Extension of Generalized Huber Loss for Robust Learning and Pseudo-Mode Statisticscited by 8
  8. 2021Efficient Locally Optimal Number Set Partitioning for Scheduling, Allocation and Fair Selectioncited by 4
  9. 2021A Quadratic Time Locally Optimal Algorithm for NP-hard Equal Cardinality Partition Optimizationcited by 3
  10. 2022A Linearithmic Time Locally Optimal Algorithm for the Multiway Number Partition Optimizationcited by 2

Built on by

Not cited yet.