A Quadratic Time Locally Optimal Algorithm for NP-hard Equal Cardinality Partition Optimization

• URL: http://arxiv.org/abs/2109.07882v1
• Date: Thu, 16 Sep 2021 11:25:18 GMT
• Title: A Quadratic Time Locally Optimal Algorithm for NP-hard Equal Cardinality Partition Optimization
• Authors: Kaan Gokcesu, Hakan Gokcesu
• Abstract summary: 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.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the optimization version of the equal cardinality set partition problem (where the absolute difference between the equal sized partitions' sums are minimized). While this problem is NP-hard and requires exponential complexity to solve in general, we have formulated a weaker version of this NP-hard problem, where the goal is to find a locally optimal solution. The local optimality considered in our work is under any swap between the opposing partitions' element pairs. To this end, we designed an algorithm which can produce such a locally optimal solution in $O(N^2)$ time and $O(N)$ space. Our approach does not require positive or integer inputs and works equally well under arbitrary input precisions. Thus, it is widely applicable in different problem scenarios.

Related papers

• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  We propose two variance reduced ZO estimators for complex gradient problems. We improve the state-of-the-art function complexities from $mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$ to $tildecalOleft(fracdepsilon2right)$.
  arXiv  Detail & Related papers  (2024-10-03T15:04:01Z)
• Approximation Algorithms for Preference Aggregation Using CP-Nets [3.337244446073836]
  This paper studies the design and analysis of approximation algorithms for aggregating preferences over Conditional Preference Networks (CP-nets) Its focus is on aggregating preferences over so-called emphswaps, for which optimal solutions in general are already known to be of exponential size.
  arXiv  Detail & Related papers  (2023-12-14T17:31:38Z)
• 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)
• Efficient Locally Optimal Number Set Partitioning for Scheduling, Allocation and Fair Selection [0.0]
  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.
  arXiv  Detail & Related papers  (2021-09-10T11:53:34Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  We consider the global minimization of smooth functions based solely on function evaluations. In this paper, we consider an approach that jointly models the function to approximate and finds a global minimum.
  arXiv  Detail & Related papers  (2020-12-22T12:59:30Z)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  Bilevel optimization is a class of problems which exhibit a two-level structure. We propose a two-timescale approximation (TTSA) algorithm for tackling such a bilevel problem. We show that a two-timescale natural actor-critic policy optimization algorithm can be viewed as a special case of our TTSA framework.
  arXiv  Detail & Related papers  (2020-07-10T05:20:02Z)
• 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)
• Second-order Conditional Gradient Sliding [79.66739383117232]
  We present the emphSecond-Order Conditional Gradient Sliding (SOCGS) algorithm. The SOCGS algorithm converges quadratically in primal gap after a finite number of linearly convergent iterations. It is useful when the feasible region can only be accessed efficiently through a linear optimization oracle.
  arXiv  Detail & Related papers  (2020-02-20T17:52:18Z)

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.