论文标题
多路数分区优化的线性时间局部最佳算法
A Linearithmic Time Locally Optimal Algorithm for the Multiway Number Partition Optimization
论文作者
论文摘要
我们研究了多路数分区优化的问题，该优化在决策，学习和优化文献中都有无数的应用。即使原始的多路分区问题是NP-硬化，并且需要指数时间复杂性算法；我们制定了一个更容易的优化问题，我们的目标是找到本地最佳的解决方案。我们提出了一个线性的时间复杂性$ O（N \ log n）$算法，该算法可以产生这种本地最佳解决方案。我们的方法对输入是鲁棒的，并且既不需要积极的和整数输入。
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.
