論文の概要: Online Matching in Sparse Random Graphs: Non-Asymptotic Performances of Greedy Algorithm

• arxiv url: http://arxiv.org/abs/2107.00995v1
• Date: Fri, 2 Jul 2021 12:18:19 GMT
• ステータス: 処理完了
• システム内更新日: 2021-07-05 12:45:32.837250
• Title: Online Matching in Sparse Random Graphs: Non-Asymptotic Performances of Greedy Algorithm
• Title（参考訳）: スパースランダムグラフにおけるオンラインマッチング:グリーディアルゴリズムの非漸近的性能
• Authors: Nathan Noiry, Flore Sentenac, Vianney Perchet
• Abstract要約: 我々は、最も単純なアルゴリズムであるGREEDYの競合比を、関連する離散過程を連続的に近似することによって推定する。 驚くべきことに、GREEDYは、オンラインマッチングのためのもう1つの有名なアルゴリズムであるRANKINGよりも優れたパフォーマンスを保証することができる。
• 参考スコア（独自算出の注目度）: 20.582965700659788
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Motivated by sequential budgeted allocation problems, we investigate online matching problems where connections between vertices are not i.i.d., but they have fixed degree distributions -- the so-called configuration model. We estimate the competitive ratio of the simplest algorithm, GREEDY, by approximating some relevant stochastic discrete processes by their continuous counterparts, that are solutions of an explicit system of partial differential equations. This technique gives precise bounds on the estimation errors, with arbitrarily high probability as the problem size increases. In particular, it allows the formal comparison between different configuration models. We also prove that, quite surprisingly, GREEDY can have better performance guarantees than RANKING, another celebrated algorithm for online matching that usually outperforms the former.
• Abstract（参考訳）: 逐次予算配分問題により、頂点間の接続がi.d.ではなく、固定度分布(いわゆる構成モデル)を持つオンラインマッチング問題を調査する。 偏微分方程式の明示的な系の解であるそれらの連続的な対応によって関連する確率的離散過程を近似することにより、最も単純なアルゴリズムであるgreedyの競合比を推定する。 この手法は、問題のサイズが大きくなるにつれて任意に高い確率で、推定誤差の正確な境界を与える。 特に、異なる構成モデル間の形式的な比較を可能にする。 また、非常に驚くべきことに、GREEDYがRANKINGよりも優れたパフォーマンス保証が得られることを証明しています。

関連論文リスト

• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Efficient distributed representations with linear-time attention scores normalization [3.8673630752805437]
  本研究では,有界ノルムを持つ埋め込みベクトルに対するアテンションスコア正規化定数の線形時間近似を提案する。 推定公式の精度は、競合するカーネルメソッドを桁違いに上回る。 提案アルゴリズムは高度に解釈可能であり,任意の埋め込み問題に容易に適応できる。
  論文  参考訳（メタデータ） (2023-03-30T15:48:26Z)
• Optimal Clustering with Bandit Feedback [57.672609011609886]
  本稿では,バンディットフィードバックを用いたオンラインクラスタリングの問題点について考察する。 これは、NPハード重み付きクラスタリング問題をサブルーチンとして解決する必要性を回避するための、シーケンシャルなテストのための新しい停止規則を含む。 合成および実世界のデータセットの広範なシミュレーションを通して、BOCの性能は下界と一致し、非適応的ベースラインアルゴリズムよりも大幅に優れることを示す。
  論文  参考訳（メタデータ） (2022-02-09T06:05:05Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  グラフマッチングアルゴリズムは、クエリグラフの埋め込みをデータグラフGに列挙する。 マッチング順序は、これらのバックトラックに基づくサブグラフマッチングアルゴリズムの時間効率において重要な役割を果たす。 本稿では,Reinforcement Learning (RL) と Graph Neural Networks (GNN) 技術を適用して,グラフマッチングアルゴリズムの高品質なマッチング順序を生成する。
  論文  参考訳（メタデータ） (2022-01-25T00:10:03Z)
• Deep Probabilistic Graph Matching [72.6690550634166]
  本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。 提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
  論文  参考訳（メタデータ） (2022-01-05T13:37:27Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。 オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。 本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
  論文  参考訳（メタデータ） (2021-11-23T18:10:48Z)
• Kernel Clustering with Sigmoid-based Regularization for Efficient Segmentation of Sequential Data [3.8326963933937885]
  セグメント化は、データシーケンスを非線形で複雑な構造を持つ複数の重複しないセグメントに分割することを目的としている。 この問題を最適に解決するための一般的なカーネルは動的プログラミング(DP)である。 最適セグメンテーションを近似するために多くのアルゴリズムが提案されているが、それらの解の品質は保証されていない。
  論文  参考訳（メタデータ） (2021-06-22T04:32:21Z)
• Efficient Permutation Discovery in Causal DAGs [9.22466799504763]
  有向非巡回グラフのスパース置換を求めるアルゴリズムを提案する。 We show that our method with depth $w$ run in $O(pw+3) $ time。 また,PC アルゴリズムや GES, GSP などの因果構造学習アルゴリズムと比較し,より短い実行時間で同等の性能が得られることを示す。
  論文  参考訳（メタデータ） (2020-11-06T21:56:41Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)

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

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