Fugu-MT 論文翻訳(概要): A 2-opt Algorithm for Locally Optimal Set Partition Optimization

論文の概要: A 2-opt Algorithm for Locally Optimal Set Partition Optimization

arxiv url: http://arxiv.org/abs/2303.08219v1
Date: Tue, 14 Mar 2023 20:25:56 GMT
ステータス: 処理完了
システム内更新日: 2023-03-16 18:36:00.256016
Title: A 2-opt Algorithm for Locally Optimal Set Partition Optimization
Title（参考訳）: 局所最適集合分割最適化のための2オプトアルゴリズム
Authors: Kaan Gokcesu, Hakan Gokcesu
Abstract要約: 我々は,最大$O(N2)$時間と$O(N)$空間で局所最適解を生成するアルゴリズムを開発した。アルゴリズムは任意の入力精度を処理でき、正や整数の入力を必要としない。
参考スコア（独自算出の注目度）: 0.0
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Our research deals with the optimization version of the set partition problem, where the objective is to minimize the absolute difference between the sums of the two disjoint partitions. Although this problem is known to be NP-hard and requires exponential time to solve, we propose a less demanding version of this problem where the goal is to find a locally optimal solution. In our approach, we consider the local optimality in respect to any movement of at most two elements. To accomplish this, we developed an algorithm that can generate a locally optimal solution in at most $O(N^2)$ time and $O(N)$ space. Our algorithm can handle arbitrary input precisions and does not require positive or integer inputs. Hence, it can be applied in various problem scenarios with ease.
Abstract（参考訳）: 本研究は,2つの分割の和の絶対差を最小化することを目的とした,集合分割問題の最適化版を扱う。この問題はNPハードであることが知られており、解くのに指数時間を要するが、局所最適解を見つけることが目的であるこの問題のより要求の少ないバージョンを提案する。提案手法では,少なくとも2つの要素の移動に関して局所最適性を検討する。そこで我々は,少なくとも$O(N^2)$時間と$O(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)
An Algorithm with Optimal Dimension-Dependence for Zero-Order Nonsmooth Nonconvex Stochastic Optimization [37.300102993926046]
リプシッツの目的の滑らかな点も凸点も生成しない点の複雑さについて検討する。私たちの分析は単純だが強力だ。 Goldstein-subdifferential set, これは最近の進歩を可能にする。非滑らかな非最適化
論文参考訳（メタデータ） (2023-07-10T11:56:04Z)
A Linearithmic Time Locally Optimal Algorithm for the Multiway Number Partition Optimization [0.0]
マルチウェイ数分割最適化の問題について検討する。我々は、そのような局所最適解を生成できる線形時間複雑性$O(Nlog N)$アルゴリズムを提案する。
論文参考訳（メタデータ） (2022-03-10T20:07:21Z)
A Quadratic Time Locally Optimal Algorithm for NP-hard Equal Cardinality Partition Optimization [0.0]
等濃度集合分割問題の最適化版(等値分割の和の絶対差を最小化する)について検討する。我々のアプローチでは正あるいは整数の入力は必要とせず、任意の入力精度で同じように機能する。
論文参考訳（メタデータ） (2021-09-16T11:25:18Z)
Efficient Locally Optimal Number Set Partitioning for Scheduling, Allocation and Fair Selection [0.0]
提案アルゴリズムは, ほぼ線形時間で局所最適解を求めることができることを示す。我々のアルゴリズムは入力集合に正の要素も整数の要素も必要としないので、より広く適用できる。
論文参考訳（メタデータ） (2021-09-10T11:53:34Z)
Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
論文参考訳（メタデータ） (2021-06-08T15:54:44Z)
Instance Specific Approximations for Submodular Maximization [45.91235224228292]
実世界のインスタンス上で最適な解に対して,アルゴリズムの性能をベンチマークする手法を模索する。大きな疑問は、実際に遭遇したインスタンスの最適なソリューションと比較して、アルゴリズムのパフォーマンスを測定する方法です。我々の主な貢献は、サブモジュラー最小化のための新しいアルゴリズムではなく、サブモジュラーインスタンスのアルゴリズムがいかに最適かを測定する分析手法である。
論文参考訳（メタデータ） (2021-02-23T19:39:32Z)
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)
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)

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