Fugu-MT 論文翻訳(概要): A Linearithmic Time Locally Optimal Algorithm for the Multiway Number Partition Optimization

論文の概要: A Linearithmic Time Locally Optimal Algorithm for the Multiway Number Partition Optimization

arxiv url: http://arxiv.org/abs/2203.05618v1
Date: Thu, 10 Mar 2022 20:07:21 GMT
ステータス: 処理完了
システム内更新日: 2022-03-14 13:42:49.897876
Title: A Linearithmic Time Locally Optimal Algorithm for the Multiway Number Partition Optimization
Title（参考訳）: 多路数分割最適化のための線形時間局所最適アルゴリズム
Authors: Kaan Gokcesu, Hakan Gokcesu
Abstract要約: マルチウェイ数分割最適化の問題について検討する。我々は、そのような局所最適解を生成できる線形時間複雑性$O(Nlog N)$アルゴリズムを提案する。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We study the problem of multiway number partition optimization, which has a myriad of applications in the decision, learning and optimization literature. Even though the original multiway partitioning problem is NP-hard and requires exponential time complexity algorithms; we formulate an easier optimization problem, where our goal is to find a solution that is locally optimal. We propose a linearithmic time complexity $O(N\log N)$ algorithm that can produce such a locally optimal solution. Our method is robust against the input and requires neither positive nor integer inputs.
Abstract（参考訳）: 決定,学習,最適化の文献に無数の応用があるマルチウェイ数分割最適化の問題について検討する。もともとのマルチウェイ分割問題はnp-hardであり、指数関数的時間複雑性アルゴリズムを必要とするが、我々はより簡単な最適化問題を定式化している。このような局所最適解を生成できる線形時間複雑性$o(n\log n)$アルゴリズムを提案する。我々の手法は入力に対して堅牢であり、正の入力も整数の入力も不要である。

関連論文リスト

Learning Multiple Initial Solutions to Optimization Problems [52.9380464408756]
厳密なランタイム制約の下で、同様の最適化問題を順次解決することは、多くのアプリケーションにとって不可欠である。本稿では,問題インスタンスを定義するパラメータが与えられた初期解を多種多様に予測する学習を提案する。提案手法は,すべての評価設定において有意かつ一貫した改善を実現し,必要な初期解の数に応じて効率よくスケールできることを実証した。
論文参考訳（メタデータ） (2024-11-04T15:17:19Z)
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 Quadratic Time Locally Optimal Algorithm for NP-hard Equal Cardinality Partition Optimization [0.0]
等濃度集合分割問題の最適化版(等値分割の和の絶対差を最小化する)について検討する。我々のアプローチでは正あるいは整数の入力は必要とせず、任意の入力精度で同じように機能する。
論文参考訳（メタデータ） (2021-09-16T11:25:18Z)
Choosing the Right Algorithm With Hints From Complexity Theory [16.33500498939925]
我々は,メトロポリスのアルゴリズムが,合理的な問題サイズを考慮に入れた全てのアルゴリズムの中で,明らかに最良のものであることを示す。このタイプの人工アルゴリズムは、$O(n log n)$ランタイムを持つので、重要度に基づくコンパクト遺伝的アルゴリズム(sig-cGA)は、高い確率で、DLB問題を解くことができる。
論文参考訳（メタデータ） (2021-09-14T11:12:32Z)
Efficient Locally Optimal Number Set Partitioning for Scheduling, Allocation and Fair Selection [0.0]
提案アルゴリズムは, ほぼ線形時間で局所最適解を求めることができることを示す。我々のアルゴリズムは入力集合に正の要素も整数の要素も必要としないので、より広く適用できる。
論文参考訳（メタデータ） (2021-09-10T11:53:34Z)
Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。両レベル最適化のための2つの新しいアルゴリズムを提案する。両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文参考訳（メタデータ） (2021-06-08T21:05:30Z)
Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文参考訳（メタデータ） (2021-01-07T08:00:02Z)
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)

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