mlsanityData to 7 Oct 2026

Efficient Locally Optimal Number Set Partitioning for Scheduling, Allocation and Fair Selection

arXiv 2109.04809 ↗First posted 10 Sep 2021cs.DS cs.LG math.COcited by 4

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 4 of its 50 references that are in the map. First posted on arXiv 10 Sep 2021.

Builds on

4 of 50 references.

References · 4

  1. 2021Generalized Huber Loss for Robust Learning and its Efficient Minimization for a Robust Statisticscited by 32
  2. 2021Optimally Efficient Sequential Calibration of Binary Classifiers to Minimize Classification Errorcited by 17
  3. 2020Recursive Experts: An Efficient Optimal Mixture of Learning Systems in Dynamic Environmentscited by 15
  4. 2021Optimal and Efficient Algorithms for General Mixable Losses against Switching Oraclescited by 10

Built on by

Cited by year

Citing papers per year: 2021: 1; 2022: 2; 2023: 1.

4 papers.

  1. 2021A Quadratic Time Locally Optimal Algorithm for NP-hard Equal Cardinality Partition Optimizationcited by 3
  2. 2022A Linearithmic Time Locally Optimal Algorithm for the Multiway Number Partition Optimizationcited by 2
  3. 2022Merging Knockout and Round-Robin Tournaments: A Flexible Linear Elimination Tournament Designcited by 0
  4. 2023A 2-opt Algorithm for Locally Optimal Set Partition Optimizationcited by 0