論文の概要: Near-Optimal Coalition Structures in Polynomial Time

• arxiv url: http://arxiv.org/abs/2512.21657v1
• Date: Thu, 25 Dec 2025 12:56:37 GMT
• ステータス: 情報取得中
• システム内更新日: 2025-12-29 12:04:54.729415
• Title: Near-Optimal Coalition Structures in Polynomial Time
• Title（参考訳）: 多項式時間における準最適結合構造
• Authors: Angshul Majumdar,
• Abstract要約: 疎緩緩和は、福祉が適度に最適品質に近い連立構造を高い確率で回復させることを示す。 これにより、厳密な確率的分離が確立され、厳密な解法は究極的には最適であるにもかかわらず、緩やかな緩和が望まれる。
• 参考スコア（独自算出の注目度）: 11.62669179647184
• License:
• Abstract: We study the classical coalition structure generation (CSG) problem and compare the anytime behavior of three algorithmic paradigms: dynamic programming (DP), MILP branch-and-bound, and sparse relaxations based on greedy or $l_1$-type methods. Under a simple random "sparse synergy" model for coalition values, we prove that sparse relaxations recover coalition structures whose welfare is arbitrarily close to optimal in polynomial time with high probability. In contrast, broad classes of DP and MILP algorithms require exponential time before attaining comparable solution quality. This establishes a rigorous probabilistic anytime separation in favor of sparse relaxations, even though exact methods remain ultimately optimal.
• Abstract（参考訳）: 古典的連立構造生成(CSG)問題について検討し、動的プログラミング(DP)、MILP分岐結合(MILP branch-and-bound)、スパース緩和(sparse relaxation)という3つのアルゴリズムパラダイムの時相挙動をgreedy法や$l_1$-type法に基づいて比較する。 単純なランダムな「スパースシナジー」モデルの下では、スパース緩和により、多項式時間における福祉が任意に最適に近い連立構造が高確率で回復することが証明される。 対照的に、DPとMILPアルゴリズムの幅広いクラスは、同等のソリューション品質に達するまでに指数時間を必要とする。 これにより、厳密な確率的分離が確立され、厳密な解法は究極的には最適であるにもかかわらず、緩やかな緩和が望まれる。

関連論文リスト

• Towards Fast Algorithms for the Preference Consistency Problem Based on Hierarchical Models [4.007697401483925]
  階層モデルに基づく選好文の一貫性問題の解法として,アルゴリズム的手法を構築し,比較する。 インスタンスが一貫すると、評価関数に階層的モデルが存在し、代替関数の順序関係を誘導する。 この問題を解決するための3つのアプローチを開発する。
  論文  参考訳（メタデータ） (2024-10-31T13:48:46Z)
• Differentially Private Optimization with Sparse Gradients [60.853074897282625]
  微分プライベート(DP)最適化問題を個人勾配の空間性の下で検討する。 これに基づいて、スパース勾配の凸最適化にほぼ最適な速度で純粋および近似DPアルゴリズムを得る。
  論文  参考訳（メタデータ） (2024-04-16T20:01:10Z)
• Efficient Global Planning in Large MDPs via Stochastic Primal-Dual Optimization [12.411844611718958]
  提案手法は, 生成モデルに対する多数のクエリの後に, ほぼ最適ポリシーを出力することを示す。 提案手法は計算効率が高く,低次元パラメータベクトルでコンパクトに表現される単一のソフトマックスポリシーを出力する点が大きな利点である。
  論文  参考訳（メタデータ） (2022-10-21T15:49:20Z)
• Discrete-Convex-Analysis-Based Framework for Warm-Starting Algorithms with Predictions [15.191184049312467]
  アルゴリズムを学習した予測で拡張することは、最悪の場合の境界を越えるための有望なアプローチである。 学習された双対解による温かいスタートは、重み付き完全二分法マッチングのためのハンガリーの手法の時間的複雑さを改善することができることを示す。 重み付き完全二部構造マッチング,重み付きマトロイド交叉,離散エネルギー最小化に適用することで,DCAベースのフレームワークの有用性を示す。
  論文  参考訳（メタデータ） (2022-05-20T04:49:57Z)
• Efficient semidefinite bounds for multi-label discrete graphical models [6.226454551201676]
  このようなモデルにおける主要なクエリの1つは、Posteri(MAP)ネットワークのコストに関するSDPWCSP関数を特定することである。 従来の二重化制約手法と,行ごとの更新に基づく専用SDP/Monteiroスタイルの手法を検討する。
  論文  参考訳（メタデータ） (2021-11-24T13:38:34Z)
• Grouped Variable Selection with Discrete Optimization: Computational and Statistical Perspectives [9.593208961737572]
  本稿では,離散数理最適化に基づくグループ変数選択のための新しいアルゴリズムフレームワークを提案する。 本手法は,スパースプログラミングを用いた高次元線形回帰法と非加法モデリングの両方を網羅する。 提案手法は,関連する混合整数問題(mip)を解き,最適性が証明できるスタンドアロンの分岐・境界(bnb)フレームワークに基づいている。
  論文  参考訳（メタデータ） (2021-04-14T19:21:59Z)
• Doubly Robust Off-Policy Actor-Critic: Convergence and Optimality [131.45028999325797]
  ディスカウント型MDPのための2倍堅牢なオフポリチックAC(DR-Off-PAC)を開発した。 DR-Off-PACは、俳優と批評家の両方が一定のステップで同時に更新される単一のタイムスケール構造を採用しています。 有限時間収束速度を研究し, dr-off-pac のサンプル複雑性を特徴とし, $epsilon$-accurate optimal policy を得る。
  論文  参考訳（メタデータ） (2021-02-23T18:56:13Z)
• Efficient semidefinite-programming-based inference for binary and multi-class MRFs [83.09715052229782]
  分割関数やMAP推定をペアワイズMRFで効率的に計算する手法を提案する。 一般のバイナリMRFから完全多クラス設定への半定緩和を拡張し、解法を用いて再び効率的に解けるようなコンパクトな半定緩和を開発する。
  論文  参考訳（メタデータ） (2020-12-04T15:36:29Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis [102.29671176698373]
  我々は、割引決定過程における政策評価の問題に対処し、生成モデルの下で、ll_infty$errorに対するマルコフに依存した保証を提供する。 我々は、ポリシー評価のために、局所ミニマックス下限の両漸近バージョンと非漸近バージョンを確立し、アルゴリズムを比較するためのインスタンス依存ベースラインを提供する。
  論文  参考訳（メタデータ） (2020-03-16T17:15:28Z)

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

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