Efficient Locally Optimal Number Set Partitioning for Scheduling, Allocation and Fair Selection
arXiv:2109.04809
Abstract
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.
References in corpus (6)
- Where are the really hard manipulation problems? The phase transition in manipulating the veto rule
- Generalized Huber Loss for Robust Learning and its Efficient Minimization for a Robust Statistics
- A Generalized Online Algorithm for Translation and Scale Invariant Prediction with Expert Advice
- Recursive Experts: An Efficient Optimal Mixture of Learning Systems in Dynamic Environments
- Optimally Efficient Sequential Calibration of Binary Classifiers to Minimize Classification Error
- Optimal and Efficient Algorithms for General Mixable Losses against Switching Oracles