論文の概要: Exploiting Low-Rank Structure in Max-K-Cut Problems

• arxiv url: http://arxiv.org/abs/2602.20376v1
• Date: Mon, 23 Feb 2026 21:29:47 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-26 13:37:25.500239
• Title: Exploiting Low-Rank Structure in Max-K-Cut Problems
• Title（参考訳）: Max-K-Cut問題における低ランク構造の生成
• Authors: Ria Stevens, Fangshuo Liao, Barbara Su, Jianqiang Li, Anastasios Kyrillidis,
• Abstract要約: 複素二次形式をK$の領域上で最大化するアルゴリズムを提案する。 我々は、この集合が$K=3$のときに正確な最大値を含むことが保証され、目的がローランクであることを証明する。 この構成により、Max-3-Cut に対して本質的に並列化可能で理論上動機づけられたアルゴリズムのファミリーが誕生する。
• 参考スコア（独自算出の注目度）: 13.558739762168443
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We approach the Max-3-Cut problem through the lens of maximizing complex-valued quadratic forms and demonstrate that low-rank structure in the objective matrix can be exploited, leading to alternative algorithms to classical semidefinite programming (SDP) relaxations and heuristic techniques. We propose an algorithm for maximizing these quadratic forms over a domain of size $K$ that enumerates and evaluates a set of $O\left(n^{2r-1}\right)$ candidate solutions, where $n$ is the dimension of the matrix and $r$ represents the rank of an approximation of the objective. We prove that this candidate set is guaranteed to include the exact maximizer when $K=3$ (corresponding to Max-3-Cut) and the objective is low-rank, and provide approximation guarantees when the objective is a perturbation of a low-rank matrix. This construction results in a family of novel, inherently parallelizable and theoretically-motivated algorithms for Max-3-Cut. Extensive experimental results demonstrate that our approach achieves performance comparable to existing algorithms across a wide range of graphs, while being highly scalable.
• Abstract（参考訳）: 我々は、複素数値二次形式を最大化するレンズを通してMax-3-Cut問題にアプローチし、目的行列の低ランク構造を活用できることを示し、古典的半定値プログラミング(SDP)緩和やヒューリスティック手法に代わるアルゴリズムを導いた。 我々は、これらの二次形式を最大化するためのアルゴリズムを提案し、このアルゴリズムは、$O\left(n^{2r-1}\right)$の候補解を列挙し、評価する。 我々は、この候補集合が、$K=3$(Max-3-Cutに対応する)のときの正確な最大値を含むことが保証され、その目的が低ランク行列の摂動であるときの近似保証を提供する。 この構成により、Max-3-Cut に対して本質的に並列化可能で理論上動機づけられたアルゴリズムのファミリーが誕生する。 大規模な実験結果から,提案手法は広範囲のグラフにまたがる既存のアルゴリズムに匹敵する性能を達成できるが,高いスケーラビリティを実現することができる。

関連論文リスト

• FraPPE: Fast and Efficient Preference-based Pure Exploration [17.53646399595373]
  任意の選好円錐に対して既存の下界を最適に追跡する効率的なアルゴリズムを提案する。 提案したPrePExアルゴリズムであるFraPPEが最適なサンプル複雑性を実現することを証明した。
  論文  参考訳（メタデータ） (2025-08-22T16:02:06Z)
• EXOTIC: An Exact, Optimistic, Tree-Based Algorithm for Min-Max Optimization [3.249853429482705]
  ミニマックス最適化は、ゲーム理論、機械対向学習などの分野において、勾配に基づく手法を典型的なツールとして現れる。 本稿では,凸型手法におけるグローバル最適解をアルゴリズムで計算する手法を提案する。 次に,EXOTIC Exactを紹介する。 反復的に内部楽観的な木に基づく解法で外楽観的な領域を(ほぼ)解決する クラスの呼び出し数の内部への呼び出し数。
  論文  参考訳（メタデータ） (2025-08-17T19:39:19Z)
• Learning-Augmented Hierarchical Clustering [29.438861266606573]
  自然のオラクルから補助情報を得た階層的クラスタリングの問題を考察する。 分割オラクルは、アルゴリズムが標準のHCアプローチより優れていることを示す。 我々のアプローチはサブ線形設定にまで拡張され、保証を改善した新しいストリーミングとPRAMアルゴリズムが示されます。
  論文  参考訳（メタデータ） (2025-06-05T18:22:40Z)
• Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
  離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。 また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。 我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
  論文  参考訳（メタデータ） (2025-02-07T15:57:56Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  測定から学習した線形モデルの定量化の問題を考える。 この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。 本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-23T02:39:04Z)
• A stochastic linearized proximal method of multipliers for convex stochastic optimization with expectation constraints [8.133190610747974]
  計算可能近似型アルゴリズム,すなわち乗算器の線形化近近凸法を提案する。 予備的な数値計算の結果は,提案アルゴリズムの性能を示すものである。
  論文  参考訳（メタデータ） (2021-06-22T07:24:17Z)
• Minimax Optimization with Smooth Algorithmic Adversaries [59.47122537182611]
  対戦相手が展開するスムーズなアルゴリズムに対して,Min-playerの新しいアルゴリズムを提案する。 本アルゴリズムは,制限周期のない単調進行を保証し,適切な勾配上昇数を求める。
  論文  参考訳（メタデータ） (2021-06-02T22:03:36Z)
• Joint Optimization of Multi-Objective Reinforcement Learning with Policy Gradient Based Algorithm [50.50545326342971]
  複数の長期目標の非線形凹関数を最大化する問題を定式化する。 この問題に対してポリシー段階に基づくモデルフリーアルゴリズムを提案する。 提案アルゴリズムは,グローバルオプティマの$epsilon$以内に収束することが示されている。
  論文  参考訳（メタデータ） (2021-05-28T22:20:54Z)
• Hybrid Trilinear and Bilinear Programming for Aligning Partially Overlapping Point Sets [85.71360365315128]
  多くの応用において、部分重なり合う点集合が対応するRPMアルゴリズムに不変であるようなアルゴリズムが必要である。 まず、目的が立方体有界関数であることを示し、次に、三線型および双線型単相変換の凸エンベロープを用いて、その下界を導出する。 次に、変換変数上の分岐のみを効率よく実行するブランチ・アンド・バウンド(BnB)アルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-01-19T04:24:23Z)
• 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)

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

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