Efficient Locally Optimal Number Set Partitioning for Scheduling, Allocation and Fair Selection
This provides efficient approximate solutions for scheduling, allocation, and fair selection problems where exact optimization is intractable.
The authors tackled the NP-hard set partition optimization problem by formulating a weaker version seeking locally optimal solutions, and showed their algorithms can find such solutions in near linear time while working with arbitrary numeric inputs.
We study the optimization version of the set partition problem (where the difference between the partition sums are minimized), which has numerous applications in decision theory literature. While the set partitioning problem is NP-hard and requires exponential complexity to solve (i.e., intractable); we formulate a weaker version of this NP-hard problem, where the goal is to find a locally optimal solution. We show that our proposed algorithms can find a locally optimal solution in near linear time. Our algorithms require neither positive nor integer elements in the input set, hence, they are more widely applicable.