論文の概要: Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)

• arxiv url: http://arxiv.org/abs/2411.10453v1
• Date: Thu, 31 Oct 2024 09:26:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-24 06:02:02.982649
• Title: Towards Geometry-Preserving Reductions Between Constraint Satisfaction Problems (and other problems in NP)
• Title（参考訳）: 制約満足度問題(およびその他のNP問題)の幾何保存化に向けて
• Authors: Gabriel Istrate,
• Abstract要約: 我々は,制約満足度問題と他のNP-search問題との2種類の幾何保存還元を定義する。 これらの削減について、いくつかの例と反例を挙げる。
• 参考スコア（独自算出の注目度）: 0.0
• License:
• Abstract: Motivated by phase transitions in combinatorial optimization problems, we define two kinds of geometry-preserving reductions between constraint satisfaction problems and other NP-search problems. We give a couple of examples and counterexamples for these reductions.
• Abstract（参考訳）: 組合せ最適化問題における位相遷移により、制約満足度問題と他のNP探索問題の間の幾何保存還元を2種類定義する。 これらの削減について、いくつかの例と反例を挙げる。

関連論文リスト

• WANCO: Weak Adversarial Networks for Constrained Optimization problems [5.257895611010853]
  まず、拡張ラグランジアン法を用いてミニマックス問題をミニマックス問題に変換する。 次に、それぞれ原始変数と双対変数を表すために、2つの(または複数の)ディープニューラルネットワークを使用します。 ニューラルネットワークのパラメータは、敵のプロセスによって訓練される。
  論文  参考訳（メタデータ） (2024-07-04T05:37:48Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。 我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。 本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
  論文  参考訳（メタデータ） (2023-10-08T23:39:38Z)
• Hybrid Quantum Algorithms integrating QAOA, Penalty Dephasing and Zeno Effect for Solving Binary Optimization Problems with Multiple Constraints [5.259170150405252]
  本稿では,制約のサブセットを解決するために標準イジング・ハミルトニアン(Ising Hamiltonian)を併用したハイブリッドフレームワークを提案する。 これらの非Ising制約の解決は、ペナルティの軽視または量子ゼノ効果によって達成される。
  論文  参考訳（メタデータ） (2023-05-14T03:49:10Z)
• Structured Low-Rank Tensor Learning [2.1227526213206542]
  構造制約のある部分的な観測から低ランクテンソルを学習する問題を考察する。 このようなテンソルの新たな分解法を提案し、より単純な最適化問題を導いた。
  論文  参考訳（メタデータ） (2023-05-13T17:04:54Z)
• Approximation of optimization problems with constraints through kernel Sum-Of-Squares [77.27820145069515]
  我々は、点的不等式が非負の kSoS 関数のクラス内で等式となることを示す。 また, 等式制約に焦点をあてることで, 散乱不等式を用いることで, 制約のサンプリングにおける次元性の呪いを軽減することができることを示す。
  論文  参考訳（メタデータ） (2023-01-16T10:30:04Z)
• A Constrained Optimization Approach to Bilevel Optimization with Multiple Inner Minima [49.320758794766185]
  そこで本研究では,両レベル問題を等価な制約付き最適化に変換する手法を提案する。 このようなアプローチには、(a)多重内極小問題への対処、(b)ジャコビアン計算のない完全一階効率など、いくつかの利点がある。
  論文  参考訳（メタデータ） (2022-03-01T18:20:01Z)
• Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep Unrolling [86.85697555068168]
  2段階のアルゴリズム最適化は、様々な工学や科学的応用において重要な役割を果たす。 特に長期変数と短期変数が制約の中で結合されている場合、アルゴリズムは効率的ではない。 PDD-SSCAが既存のソリューションよりも優れたパフォーマンスを達成できることを示します。
  論文  参考訳（メタデータ） (2021-05-05T03:36:00Z)
• Improving Constraint Satisfaction Algorithm Efficiency for the AllDifferent Constraint [0.0]
  制約満足問題(CSP: Constraint Satisfaction Problems)と記載された組合せ問題を検討する。 元のCSP用に設計され、AllDifferent制約を含む任意のアルゴリズムは、元のCSPと補完的な問題の両方に同時に適用した場合、少なくとも同じレベルの有効性を持つことを示す。
  論文  参考訳（メタデータ） (2020-12-07T12:14:55Z)
• Conditional gradient methods for stochastically constrained convex minimization [54.53786593679331]
  構造凸最適化問題に対する条件勾配に基づく2つの新しい解法を提案する。 私たちのフレームワークの最も重要な特徴は、各イテレーションで制約のサブセットだけが処理されることです。 提案アルゴリズムは, 条件勾配のステップとともに, 分散の低減と平滑化に頼り, 厳密な収束保証を伴っている。
  論文  参考訳（メタデータ） (2020-07-07T21:26:35Z)
• Joint Wasserstein Distribution Matching [89.86721884036021]
  JDM問題(Joint Distribution matching)は、2つのドメインの関節分布を一致させるために双方向マッピングを学習することを目的としており、多くの機械学習およびコンピュータビジョンアプリケーションで発生している。 2つの領域における関節分布のワッサーシュタイン距離を最小化することにより、JDM問題に対処することを提案する。 そこで我々は,難解な問題を簡単な最適化問題に還元する重要な定理を提案し,その解法を開発した。
  論文  参考訳（メタデータ） (2020-03-01T03:39:00Z)
• Quantum approximate algorithm for NP optimization problems with constraints [12.294570891467604]
  本稿では,異なる制約型を等式,線形不等式,任意の形式に定式化する。 そこで本研究では,NP最適化問題の解法としてQAOAフレームワークに適合する制約符号化方式を提案する。 提案手法の有効性と有効性を示す。
  論文  参考訳（メタデータ） (2020-02-01T04:45:41Z)

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

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