Fugu-MT 論文翻訳(概要): Strengthening neighbourhood substitution

論文の概要: Strengthening neighbourhood substitution

arxiv url: http://arxiv.org/abs/2007.06282v1
Date: Mon, 13 Jul 2020 10:06:20 GMT
ステータス: 処理完了
システム内更新日: 2022-11-10 23:58:19.425117
Title: Strengthening neighbourhood substitution
Title（参考訳）: 地域交代の強化
Authors: Martin C. Cooper
Abstract要約: 本研究では,時間的複雑さを増大させることなく,近傍置換の概念を2つの異なる方法で強化できることを示す。また、近隣の置換とは異なり、これらの新しい操作の最適なシーケンスを見つけることはNPハードである、という理論的結果も示している。
参考スコア（独自算出の注目度）: 4.56877715768796
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: Domain reduction is an essential tool for solving the constraint satisfaction problem (CSP). In the binary CSP, neighbourhood substitution consists in eliminating a value if there exists another value which can be substituted for it in each constraint. We show that the notion of neighbourhood substitution can be strengthened in two distinct ways without increasing time complexity. We also show the theoretical result that, unlike neighbourhood substitution, finding an optimal sequence of these new operations is NP-hard.
Abstract（参考訳）: ドメインリダクションは制約満足度問題(CSP)を解決するための重要なツールである。バイナリ CSP において、近傍置換は、各制約に代用できる別の値が存在する場合、その値を削除することである。近傍置換の概念は, 時間的複雑性を増すことなく, 2つの異なる方法で強化できることを示す。また、近隣の置換とは異なり、これらの新しい操作の最適なシーケンスを見つけることはNPハードであることの理論的結果を示す。

関連論文リスト

A Double Tracking Method for Optimization with Decentralized Generalized Orthogonality Constraints [4.6796315389639815]
分散最適化問題は分散制約の存在下では解決できない。目的関数の勾配と制約写像のヤコビアンを同時に追跡する新しいアルゴリズムを導入する。合成と実世界の両方のデータセットに数値的な結果を示す。
論文参考訳（メタデータ） (2024-09-08T06:57:35Z)
Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits [12.674929126684528]
我々は、プレイヤーがPアクションの中から d 個の基本アイテムを含む集合のパワーセットから選択する半帯域の問題に対処する。提案手法は半帯域フィードバックを効果的に活用し,帯域フィードバックアプローチより優れていることを示す。
論文参考訳（メタデータ） (2024-02-23T08:07:54Z)
Double Duality: Variational Primal-Dual Policy Optimization for Constrained Reinforcement Learning [132.7040981721302]
本研究では,訪問尺度の凸関数を最小化することを目的として,制約付き凸決定プロセス(MDP)について検討する。制約付き凸MDPの設計アルゴリズムは、大きな状態空間を扱うなど、いくつかの課題に直面している。
論文参考訳（メタデータ） (2024-02-16T16:35:18Z)
On the Partial Convexification for Low-Rank Spectral Optimization: Rank Bounds and Algorithms [1.7640556247739623]
低ランクスペクトル最適化問題(LSOP)は、複数の二辺行列の不等式を対象とする線形対象を最小化する。 LSOPの解法は一般にNPハードであるが、「LSOP-R」と呼ばれる部分凸化はしばしば抽出可能であり、高品質な解が得られる。
論文参考訳（メタデータ） (2023-05-12T17:46:29Z)
Simplification of Forest Classifiers and Regressors [1.8275108630751844]
本研究では,森林分類器や回帰器の枝分かれ条件をできるだけ多く共有する問題について検討する。本稿では,この問題を効率的に解くアルゴリズムを用いて,元問題に対するアルゴリズムを提案する。本手法の有効性は,21個のデータセットを用いた総合的な実験によって実証された。
論文参考訳（メタデータ） (2022-12-14T08:49:02Z)
Fully Stochastic Trust-Region Sequential Quadratic Programming for Equality-Constrained Optimization Problems [62.83783246648714]
目的と決定論的等式制約による非線形最適化問題を解くために,逐次2次プログラミングアルゴリズム(TR-StoSQP)を提案する。アルゴリズムは信頼領域半径を適応的に選択し、既存の直線探索StoSQP方式と比較して不確定なヘッセン行列を利用することができる。
論文参考訳（メタデータ） (2022-11-29T05:52:17Z)
Incremental Updates of Generalized Hypertree Decompositions [7.082768797784365]
我々は、CSP$P'$の分解を更新することで、CSP$P'$のいくつかの変更によって生成される新しいCSP$P'$の有効な分解になるよう、最初のステップを作成する。この問題は理論上は難しいが,GHDを効果的に更新するためのフレームワークを提案し,実装する。
論文参考訳（メタデータ） (2022-09-21T14:12:16Z)
Algorithm for Constrained Markov Decision Process with Linear Convergence [55.41644538483948]
エージェントは、そのコストに対する複数の制約により、期待される累積割引報酬を最大化することを目的としている。エントロピー正規化ポリシーとベイダの二重化という2つの要素を統合した新しい双対アプローチが提案されている。提案手法は(線形速度で)大域的最適値に収束することが示されている。
論文参考訳（メタデータ） (2022-06-03T16:26:38Z)
Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
論文参考訳（メタデータ） (2021-12-29T02:42:59Z)
Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
論文参考訳（メタデータ） (2021-06-30T18:32:46Z)
Dynamic Regret of Convex and Smooth Functions [93.71361250701075]
非定常環境におけるオンライン凸最適化について検討する。パフォーマンス指標として動的後悔を選択します。本研究では, 滑らかさを活かして, 動的後悔をさらに高めることが可能であることを示す。
論文参考訳（メタデータ） (2020-07-07T14:10:57Z)

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