論文の概要: A Quadratic Time Locally Optimal Algorithm for NP-hard Equal Cardinality Partition Optimization

• arxiv url: http://arxiv.org/abs/2109.07882v1
• Date: Thu, 16 Sep 2021 11:25:18 GMT
• ステータス: 処理完了
• システム内更新日: 2021-09-17 16:24:34.246544
• Title: A Quadratic Time Locally Optimal Algorithm for NP-hard Equal Cardinality Partition Optimization
• Title（参考訳）: NPハード等間隔分割最適化のための二次時間局所最適化アルゴリズム
• Authors: Kaan Gokcesu, Hakan Gokcesu
• Abstract要約: 等濃度集合分割問題の最適化版(等値分割の和の絶対差を最小化する)について検討する。 我々のアプローチでは正あるいは整数の入力は必要とせず、任意の入力精度で同じように機能する。
• 参考スコア（独自算出の注目度）: 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.
• Abstract（参考訳）: 等濃度集合分割問題(等大きさ分割の和の絶対差が最小となる場合)の最適化版について検討する。 この問題はNPハードであり、一般には指数関数的複雑性を必要とするが、我々はNPハード問題のより弱いバージョンを定式化し、そこでは局所最適解を求める。 私たちの研究で考慮される局所的最適性は、対立するパーティションの要素対間のスワップ下にある。 この目的のために、我々は、$O(N^2)$ timeと$O(N)$ spaceでそのような局所最適解を生成できるアルゴリズムを設計した。 我々のアプローチでは正あるいは整数入力は必要とせず、任意の入力精度で同じように機能する。 したがって、様々な問題シナリオで広く適用できる。

関連論文リスト

• Obtaining Lower Query Complexities through Lightweight Zeroth-Order Proximal Gradient Algorithms [65.42376001308064]
  複素勾配問題に対する2つの分散化ZO推定器を提案する。 我々は、現在最先端の機能複雑性を$mathcalOleft(minfracdn1/2epsilon2, fracdepsilon3right)$から$tildecalOleft(fracdepsilon2right)$に改善する。
  論文  参考訳（メタデータ） (2024-10-03T15:04:01Z)
• Approximation Algorithms for Preference Aggregation Using CP-Nets [3.337244446073836]
  本稿では,条件付き選好ネットワーク(CP-nets)上での選好を集約する近似アルゴリズムの設計と解析について述べる。 その焦点は、一般に最適な解が指数関数的な大きさであることが知られている、いわゆる「エンフスワップ」よりも、優先的な選好を集約することである。
  論文  参考訳（メタデータ） (2023-12-14T17:31:38Z)
• Accelerating Cutting-Plane Algorithms via Reinforcement Learning Surrogates [49.84541884653309]
  凸離散最適化問題に対する現在の標準的なアプローチは、カットプレーンアルゴリズムを使うことである。 多くの汎用カット生成アルゴリズムが存在するにもかかわらず、大規模な離散最適化問題は、難易度に悩まされ続けている。 そこで本研究では,強化学習による切削平面アルゴリズムの高速化手法を提案する。
  論文  参考訳（メタデータ） (2023-07-17T20:11:56Z)
• A 2-opt Algorithm for Locally Optimal Set Partition Optimization [0.0]
  我々は,最大$O(N2)$時間と$O(N)$空間で局所最適解を生成するアルゴリズムを開発した。 アルゴリズムは任意の入力精度を処理でき、正や整数の入力を必要としない。
  論文  参考訳（メタデータ） (2023-03-14T20:25:56Z)
• A Linearithmic Time Locally Optimal Algorithm for the Multiway Number Partition Optimization [0.0]
  マルチウェイ数分割最適化の問題について検討する。 我々は、そのような局所最適解を生成できる線形時間複雑性$O(Nlog N)$アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2022-03-10T20:07:21Z)
• Efficient Locally Optimal Number Set Partitioning for Scheduling, Allocation and Fair Selection [0.0]
  提案アルゴリズムは, ほぼ線形時間で局所最適解を求めることができることを示す。 我々のアルゴリズムは入力集合に正の要素も整数の要素も必要としないので、より広く適用できる。
  論文  参考訳（メタデータ） (2021-09-10T11:53:34Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  関数評価のみに基づく滑らかな関数のグローバル最小化を考える。 本稿では,近似関数を共同でモデル化し,大域的最小値を求める手法を検討する。
  論文  参考訳（メタデータ） (2020-12-22T12:59:30Z)
• A Two-Timescale Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic [142.1492359556374]
  双レベル最適化は、2レベル構造を示す問題のクラスである。 このような二段階問題に対処するための2段階近似(TTSA)アルゴリズムを提案する。 本稿では,TTSAフレームワークの特殊な事例として,2段階の自然なアクター・クリティカルポリシー最適化アルゴリズムが有用であることを示す。
  論文  参考訳（メタデータ） (2020-07-10T05:20:02Z)
• Partitioned Least Squares [3.372747046563984]
  新たな定式化は凸ではなく,この問題に対処するための2つの代替手法を提供する。 完全性のために、分割数が大きすぎる場合に正確な方法の代わりに使用できる代替分岐および有界アルゴリズムを提供する。
  論文  参考訳（メタデータ） (2020-06-29T17:10:32Z)
• Private Stochastic Convex Optimization: Optimal Rates in Linear Time [74.47681868973598]
  本研究では,凸損失関数の分布から得られた個体群損失を最小化する問題について検討する。 Bassilyらによる最近の研究は、$n$のサンプルを与えられた過剰な人口損失の最適境界を確立している。 本稿では,余剰損失に対する最適境界を達成するとともに,$O(minn, n2/d)$グラデーション計算を用いて凸最適化アルゴリズムを導出する2つの新しい手法について述べる。
  論文  参考訳（メタデータ） (2020-05-10T19:52:03Z)
• Second-order Conditional Gradient Sliding [79.66739383117232]
  本稿では,emphSecond-Order Conditional Gradient Sliding (SOCGS)アルゴリズムを提案する。 SOCGSアルゴリズムは、有限個の線形収束反復の後、原始ギャップに二次的に収束する。 実現可能な領域が線形最適化オラクルを通してのみ効率的にアクセスできる場合に有用である。
  論文  参考訳（メタデータ） (2020-02-20T17:52:18Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。