A Linearithmic Time Locally Optimal Algorithm for the Multiway Number Partition Optimization
Not on the map. Why?
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.
Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 9 of its 79 references that are in the map. First posted on arXiv 10 Mar 2022.
Builds on
9 of 79 references.
References · 9
- 2021Generalized Huber Loss for Robust Learning and its Efficient Minimization for a Robust Statisticscited by 32
- 2021Optimally Efficient Sequential Calibration of Binary Classifiers to Minimize Classification Errorcited by 17
- 2020Recursive Experts: An Efficient Optimal Mixture of Learning Systems in Dynamic Environmentscited by 15
- 2022Low Regret Binary Sampling Method for Efficient Global Optimization of Univariate Functionscited by 11
- 2018Fair Division Under Cardinality Constraintscited by 10
- 2021Optimal and Efficient Algorithms for General Mixable Losses against Switching Oraclescited by 10
- 2021Cumulative Regret Analysis of the Piyavskii--Shubert Algorithm and Its Variants for Global Optimizationcited by 9
- 2021Efficient Locally Optimal Number Set Partitioning for Scheduling, Allocation and Fair Selectioncited by 4
- 2021A Quadratic Time Locally Optimal Algorithm for NP-hard Equal Cardinality Partition Optimizationcited by 3
Built on by
Citing papers per year: 2022: 1; 2023: 1.
2 papers.