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

• URL: http://arxiv.org/abs/2109.04809v1
• Date: Fri, 10 Sep 2021 11:53:34 GMT
• Title: Efficient Locally Optimal Number Set Partitioning for Scheduling, Allocation and Fair Selection
• Authors: Kaan Gokcesu, Hakan Gokcesu
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

Related papers

• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  A current standard approach to solving convex discrete optimization problems is the use of cutting-plane algorithms. Despite the existence of a number of general-purpose cut-generating algorithms, large-scale discrete optimization problems continue to suffer from intractability. We propose a method for accelerating cutting-plane algorithms via reinforcement learning.
  arXiv  Detail & Related papers  (2023-07-17T20:11:56Z)
• A 2-opt Algorithm for Locally Optimal Set Partition Optimization [0.0]
  We develop an algorithm that can generate a locally optimal solution in at most $O(N2)$ time and $O(N)$ space. Our algorithm can handle arbitrary input precisions and does not require positive or integer inputs.
  arXiv  Detail & Related papers  (2023-03-14T20:25:56Z)
• A Linearithmic Time Locally Optimal Algorithm for the Multiway Number Partition Optimization [0.0]
  We study the problem of multiway number partition optimization. We propose a linearithmic time complexity $O(Nlog N)$ algorithm that can produce such a locally optimal solution.
  arXiv  Detail & Related papers  (2022-03-10T20:07:21Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  We present an end-to-end method to learn the proximal operator across non-family problems. We show that for weakly-ized objectives and under mild conditions, the method converges globally.
  arXiv  Detail & Related papers  (2022-01-28T05:53:28Z)
• A Quadratic Time Locally Optimal Algorithm for NP-hard Equal Cardinality Partition Optimization [0.0]
  We study the optimization version of the equal cardinality set partition problem (where the absolute difference between the equal sized partitions' sums are minimized) Our approach does not require positive or integer inputs and works equally well under arbitrary input precisions.
  arXiv  Detail & Related papers  (2021-09-16T11:25:18Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network. We design two optimal algorithms that attain these lower bounds. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-08T15:54:44Z)
• Bayesian Algorithm Execution: Estimating Computable Properties of Black-box Functions Using Mutual Information [78.78486761923855]
  In many real world problems, we want to infer some property of an expensive black-box function f, given a budget of T function evaluations. We present a procedure, InfoBAX, that sequentially chooses queries that maximize mutual information with respect to the algorithm's output. On these problems, InfoBAX uses up to 500 times fewer queries to f than required by the original algorithm.
  arXiv  Detail & Related papers  (2021-04-19T17:22:11Z)
• A Hybrid Quantum-Classical Heuristic to solve large-scale Integer Linear Programs [0.4925222726301578]
  We present a method that integrates any quantum algorithm capable of finding solutions to integer linear programs into the Branch-and-Price algorithm. The role of the quantum algorithm is to find integer solutions to subproblems appearing in Branch-and-Price.
  arXiv  Detail & Related papers  (2021-03-29T08:59:26Z)
• Partitioned Least Squares [3.372747046563984]
  We show that the new formulation is not convex and provide two alternative methods to deal with the problem. For the sake of completeness, we provide an alternative branch and bound algorithm that can be used in place of the exact method when the number of partitions is too large.
  arXiv  Detail & Related papers  (2020-06-29T17:10:32Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  We study the problem of minimizing the population loss given i.i.d. samples from a distribution over convex loss functions. A recent work of Bassily et al. has established the optimal bound on the excess population loss achievable given $n$ samples. We describe two new techniques for deriving convex optimization algorithms both achieving the optimal bound on excess loss and using $O(minn, n2/d)$ gradient computations.
  arXiv  Detail & Related papers  (2020-05-10T19:52:03Z)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  We propose the setting of extreme algorithm selection (XAS) where we consider fixed sets of thousands of candidate algorithms. We assess the applicability of state-of-the-art AS techniques to the XAS setting and propose approaches leveraging a dyadic feature representation.
  arXiv  Detail & Related papers  (2020-01-29T09:40:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.