A Linearithmic Time Locally Optimal Algorithm for the Multiway Number Partition Optimization
This work addresses a computationally challenging problem with applications in decision-making, learning, and optimization, though it is incremental as it focuses on local optimality rather than solving the NP-hard original problem.
The paper tackles the multiway number partition optimization problem by proposing a linearithmic time algorithm that finds a locally optimal solution, achieving O(N log N) time complexity without requiring positive or integer inputs.
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(N\log N)$ algorithm that can produce such a locally optimal solution. Our method is robust against the input and requires neither positive nor integer inputs.