論文の概要: Quadratic Differentiable Optimization For The Maximum Independent Set Problem
- arxiv url: http://arxiv.org/abs/2406.19532v5
- Date: Thu, 01 May 2025 19:23:23 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-05-05 13:22:23.256583
- Title: Quadratic Differentiable Optimization For The Maximum Independent Set Problem
- Title（参考訳）: 最大独立集合問題に対する二次微分可能最適化
- Authors: Ismail Alkhouri, Cedric Le Denmat, Yingjie Li, Cunxi Yu, Jia Liu, Rongrong Wang, Alvaro Velasquez,
- Abstract要約: 独立集合問題(MIS)を解くための新しい手法を提案する。
MIS が最大 CQO-MIS であることに注意し、すべての最大独立集合が局所勾配に基づく最小値に対応することを示す。
提案手法の有効性を,**CQO-MIS,サンプリング,データ中心アプローチと比較した。
- 参考スコア（独自算出の注目度）: 23.643727259409744
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Combinatorial Optimization (CO) addresses many important problems, including the challenging Maximum Independent Set (MIS) problem. Alongside exact and heuristic solvers, differentiable approaches have emerged, often using continuous relaxations of ReLU-based or quadratic objectives. Noting that an MIS in a graph is a Maximum Clique (MC) in its complement, we propose a new quadratic formulation for MIS by incorporating an MC term, improving convergence and exploration. We show that every maximal independent set corresponds to a local minimizer, derive conditions with respect to the MIS size, and characterize stationary points. To tackle the non-convexity of the objective, we propose optimizing several initializations in parallel using momentum-based gradient descent, complemented by an efficient MIS checking criterion derived from our theory. We dub our method as **p**arallelized **C**lique-Informed **Q**uadratic **O**ptimization for MIS (**pCQO-MIS**). Our experimental results demonstrate the effectiveness of the proposed method compared to exact, heuristic, sampling, and data-centric approaches. Notably, our method avoids the out-of-distribution tuning and reliance on (un)labeled data required by data-centric methods, while achieving superior MIS sizes and competitive runtime relative to their inference time. Additionally, a key advantage of pCQO-MIS is that, unlike exact and heuristic solvers, the runtime scales only with the number of nodes in the graph, not the number of edges. Our code is available at the GitHub repository \href{https://github.com/ledenmat/pCQO-mis-benchmark/tree/refactor}{{{pCQO-MIS}}}
- Abstract（参考訳）: 組合せ最適化(CO)は、最大独立セット(MIS)問題を含む多くの重要な問題に対処する。
厳密でヒューリスティックな解法とともに、しばしばReLUに基づく2次的目的の連続的な緩和を用いて微分可能なアプローチが出現した。
グラフ内のMISがその補集合の最大傾き(MC)であることに注意し、MC項を組み込んだMISの新しい二次定式化を提案し、収束と探索を改善した。
すべての最大独立集合が局所最小値に対応し、MISサイズに関して条件を導出し、定常点を特徴づけることを示す。
目的の非凸性に対処するため,モーメントに基づく勾配降下法を用いて並列に複数の初期化を最適化し,この理論から導出したMIS検査基準を補完する手法を提案する。
我々は、MIS (**pCQO-MIS*) に対する **p**arallelized **C**lique-Informed **Q**uadratic **O**ptimization を導出する。
実験により,提案手法の有効性を,正確な,ヒューリスティック,サンプリング,データ中心アプローチと比較した。
特に,本手法は,データ中心の手法で要求されるラベル付きデータへの非分配的チューニングや依存を回避するとともに,予測時間に対して優れたMISサイズと競合ランタイムを実現する。
さらに、pCQO-MISの重要な利点は、厳密でヒューリスティックな解法とは異なり、ランタイムはエッジの数ではなく、グラフ内のノードの数でしかスケールしないことである。
私たちのコードはGitHubリポジトリ \href{https://github.com/ledenmat/pCQO-mis-benchmark/tree/refactor}{{pCQO-MIS}}} で利用可能です。
関連論文リスト
- QAOA Parameter Transferability for Maximum Independent Set using Graph Attention Networks [1.4660766608996791]
量子近似最適化アルゴリズム(QAOA)は、ハイブリッド変分問題を解くための量子コンピューティングの有望な変分法の一つである。
本研究では,グラフ注意ネットワーク(GAT)を用いたQAOAパラメータ転送方式を提案する。
我々はMIS(HyDRAMIS)のための分散リソース認識アルゴリズムを設計し、大きな問題を小さな問題に分解する。
論文 参考訳（メタデータ） (2025-04-29T19:41:05Z) - Learning to Match Unpaired Data with Minimum Entropy Coupling [7.399561232927219]
最小エントロピー結合(Minimum Entropy Coupling)は、限界の制約を満たすとともに、合同エントロピーを最小化する。
本稿では、よく知られた生成拡散モデルを用いて、連続MEC問題の解法を提案する。
我々は,本手法が汎用的であり,課題解決に容易に利用できることを実証的に実証した。
論文 参考訳（メタデータ） (2025-03-11T14:54:14Z) - On Discriminative Probabilistic Modeling for Self-Supervised Representation Learning [85.75164588939185]
複数モーダルな)自己教師付き表現学習のための連続領域における識別確率モデル問題について検討する。
我々は、自己教師付き表現学習における現在のInfoNCEに基づくコントラスト損失の制限を明らかにするために一般化誤差解析を行う。
論文 参考訳（メタデータ） (2024-10-11T18:02:46Z) - Preference-Based Multi-Agent Reinforcement Learning: Data Coverage and Algorithmic Techniques [65.55451717632317]
PbMARL(Preference-based Multi-Agent Reinforcement Learning)について検討する。
一般ゲームにおける嗜好のみのオフラインデータセットからナッシュ平衡を同定する。
以上の結果から,PbMARLの多面的アプローチが示唆された。
論文 参考訳（メタデータ） (2024-09-01T13:14:41Z) - From Maximum Cut to Maximum Independent Set [7.250073177017239]
最大独立集合(MIS)問題も特定のイジングモデルと関係があることは以前から知られていた。
この戦略により、ランダムなエルドホス・ローニイグラフの独立数に対する近似が大幅に改善されることが判明した。
また、コーディング理論から生じるベンチマークで完全なパフォーマンスを示す。
論文 参考訳（メタデータ） (2024-08-13T09:33:41Z) - Efficient k-means with Individual Fairness via Exponential Tilting [13.72284501663574]
位置に基づくリソース割り当てのシナリオでは、全てのポイントを平等に扱うという原則を達成するために、個別に公平なクラスタリングがしばしば用いられる。
本稿では,クラスタリングにおける個別の公平性を実現することを目的とした,新しいアルゴリズムである傾きk平均(TKM)を提案する。
論文 参考訳（メタデータ） (2024-06-24T11:50:31Z) - An Efficient Difference-of-Convex Solver for Privacy Funnel [3.069335774032178]
本稿では,プライバシ・ファンネル(PF)手法の効率的な解法を提案する。
提案した直流分離は, クローズドフォーム更新方程式を導出する。
提案手法をMNISTおよびFashionデータセットを用いて評価する。
論文 参考訳（メタデータ） (2024-03-02T01:05:25Z) - Solving optimization problems with local light shift encoding on Rydberg
quantum annealers [0.0]
我々は、Rydberg量子アニールの最適化問題を解くための非ユニットディスクフレームワークを提供する。
我々の構成は、局所制御可能な光シフトを個々の量子ビットに適用する多体相互作用Rydbergシステムからなる。
我々の数値シミュレーションでは、Rydbergアニーラーを所望の多体基底状態に大域的に駆動しながら、局所分解プロトコルを実装している。
論文 参考訳（メタデータ） (2023-08-15T14:24:45Z) - On the Global Solution of Soft k-Means [159.23423824953412]
本稿では,ソフトk-平均問題の解法を全世界で提案する。
ミニマルボリュームソフトkMeans (MVSkM) と呼ばれる新しいモデルを提案する。
論文 参考訳（メタデータ） (2022-12-07T12:06:55Z) - Exploiting Temporal Structures of Cyclostationary Signals for
Data-Driven Single-Channel Source Separation [98.95383921866096]
単一チャネルソース分離(SCSS)の問題点について検討する。
我々は、様々なアプリケーション領域に特に適するサイクロ定常信号に焦点を当てる。
本稿では,最小MSE推定器と競合するU-Netアーキテクチャを用いたディープラーニング手法を提案する。
論文 参考訳（メタデータ） (2022-08-22T14:04:56Z) - Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium
Learning from Offline Datasets [101.5329678997916]
両プレイヤーゼロサムマルコフゲーム(MG)をオフライン環境で研究する。
目標は、事前収集されたデータセットに基づいて、近似的なナッシュ均衡(NE)ポリシーペアを見つけることである。
論文 参考訳（メタデータ） (2022-02-15T15:39:30Z) - Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
非家族問題における近位演算子を学習するためのエンドツーエンド手法を提案する。
本手法は,弱い目的と穏やかな条件下では,世界規模で収束することを示す。
論文 参考訳（メタデータ） (2022-01-28T05:53:28Z) - Learning What to Defer for Maximum Independent Sets [84.00112106334655]
本稿では,各段階における解の要素的決定を学習することにより,エージェントが適応的に段階数を縮小あるいは拡張する,新たなDRL方式を提案する。
提案手法を最大独立集合(MIS)問題に適用し、現状のDRL方式よりも大幅に改善したことを示す。
論文 参考訳（メタデータ） (2020-06-17T02:19:31Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。