論文の概要: Stochastic Matching via Local Sparsification

• arxiv url: http://arxiv.org/abs/2605.14195v1
• Date: Wed, 13 May 2026 23:25:15 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-15 21:45:34.538188
• Title: Stochastic Matching via Local Sparsification
• Title（参考訳）: 局所スパシフィケーションによる確率的マッチング
• Authors: Sara Ahmadian, Edith Cohen, Mohammad Roghani,
• Abstract要約: リアルタイム配車システムにおいて、主なボトルネックは、マッチ自体のタイミングではなく、しばしばローカル通信帯域幅である。 2段階の局所スペーシフィケーションフレームワークを導入することで、この課題を形式化する。 高度に制約された地方予算であっても、最適に近いグローバルマッチングが達成可能であることを示す。
• 参考スコア（独自算出の注目度）: 12.632233732703758
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The classic online stochastic matching problem typically requires immediate and irrevocable matching decisions. However, in many modern decentralized systems such as real-time ride-hailing and distributed cloud computing, the primary bottleneck is often local communication bandwidth rather than the timing of the match itself. We formalize this challenge by introducing a two-stage local sparsification framework. In this setting, arriving requests must prune their realized compatibility sets to a strict budget of $k$ edges before a central coordinator optimizes the global matching. This creates a "middle ground" between local information constraints and global optimization utility. We propose a local selection strategy, parametrized by a fractional solution of the expected instance. Theoretically, we quantify the approximation ratio as a function of the solution's {\em spread}. We prove that under sufficient spread, our sparsifier globally preserves the expected size of the maximum matching. Empirically, we demonstrate the robustness of our approach using the New York City ride-hailing datasets and adversarial synthetic benchmarks. Our results show that near-optimal global matching is achievable even with highly constrained local budgets, significantly outperforming standard online baselines.
• Abstract（参考訳）: 古典的なオンライン確率的マッチング問題は通常、即時かつ不可解なマッチング決定を必要とする。 しかし、リアルタイム配車や分散クラウドコンピューティングのような現代の分散システムでは、マッチ自体のタイミングではなく、しばしばローカル通信の帯域幅がボトルネックとなっている。 2段階の局所スペーシフィケーションフレームワークを導入することで、この課題を形式化する。 この設定では、中央コーディネータがグローバルマッチングを最適化する前に、到着した要求は、実現した互換性セットを厳格な予算で$k$ edgesにプルークしなければならない。 これにより、ローカルな情報制約とグローバルな最適化ユーティリティの間に「中間の土台」が生まれる。 予測されたインスタンスの分数解によってパラメータ化される局所選択戦略を提案する。 理論的には、近似比を解の {\em spread} の関数として定量化する。 十分な拡散下では、スパリファイアは最大マッチングの期待サイズを世界規模で保存する。 実験では、ニューヨーク市のライドシェアリングデータセットと逆合成ベンチマークを用いて、我々のアプローチの堅牢性を実証した。 この結果から, 高度に制約された地方予算でも, 準最適グローバルマッチングが達成可能であり, 標準オンラインベースラインを著しく上回っていることが明らかとなった。

関連論文リスト

• Region Matters: Efficient and Reliable Region-Aware Visual Place Recognition [46.97190804063947]
  本稿では,ロバストな識別領域モデリングと適応的再ランク付けを組み合わせたFoL++を提案する。 FoL++は、軽量なメモリフットプリントで最先端のパフォーマンスを実現し、FoLよりも推論速度を40%向上させる。
  論文  参考訳（メタデータ） (2026-04-24T09:28:35Z)
• Efficiency Follows Global-Local Decoupling [62.05489838893081]
  ConvNeurは、軽量なニューラルメモリブランチがトークンの集合にグローバルなコンテキストを集約する2分岐アーキテクチャである。 学習ゲートは、グローバルなキューが目的を絞ることなく、局所的な特徴を調整できる。 標準的な分類、検出、セグメンテーションのベンチマークでは、ConvNeurは同等または低い計算で同等の選択肢にマッチするか、超えている。
  論文  参考訳（メタデータ） (2026-03-20T02:20:16Z)
• FedSpeed: Larger Local Interval, Less Communication Round, and Higher Generalization Accuracy [84.45004766136663]
  フェデレートラーニング(Federated Learning)は、分散機械学習フレームワークである。 これは、局所的不整合最適と局所的過度な適合による頑丈なクライアントドリフトによってもたらされる非消滅バイアスに悩まされる。 本稿では,これらの問題による負の影響を軽減するために,新しい実用的手法であるFedSpeedを提案する。
  論文  参考訳（メタデータ） (2023-02-21T03:55:29Z)
• Escaping Saddle Points with Bias-Variance Reduced Local Perturbed SGD for Communication Efficient Nonconvex Distributed Learning [58.79085525115987]
  ローカル手法は通信時間を短縮する有望なアプローチの1つである。 局所的データセットが局所的損失の滑らかさよりも小さい場合,通信の複雑さは非局所的手法よりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-02-12T15:12:17Z)
• Convergence Rates of Average-Reward Multi-agent Reinforcement Learning via Randomized Linear Programming [41.30044824711509]
  我々は,グローバル報酬が地域報酬の総和であり,共同政策がエージェントの限界と州全体の可観測性に分解される場合に焦点を当てる。 エージェントが局所的なサドル点問題を解き、局所的な重み付き平均化を行うマルチエージェント拡張を開発する。 準グロブリー最適解を得るためのサンプルの複雑さは、状態空間と作用空間の濃度に対する厳密な依存と一致することを確かめる。
  論文  参考訳（メタデータ） (2021-10-22T03:48:41Z)
• Higher Performance Visual Tracking with Dual-Modal Localization [106.91097443275035]
  Visual Object Tracking (VOT)は、堅牢性と正確性の両方に同期性を必要とする。 ONRによるロバストなローカリゼーション抑制器とOFCによるターゲットセンターへの正確なローカリゼーションにより、ターゲットローカリゼーションのためのデュアルモーダルフレームワークを提案します。
  論文  参考訳（メタデータ） (2021-03-18T08:47:56Z)
• Consensus-Guided Correspondence Denoising [67.35345850146393]
  本稿では,地域間コンセンサス学習フレームワークと対応関係を異色化し,対応関係をロバストに識別する。 ローカル地域からグローバル地域への動的グラフから推定されるコンセンサススコアに基づいて,信頼度の高い候補を初期マッチングから蒸留する新しい「プルーニング」ブロックを導入した。 本手法は、堅牢なラインフィッティング、ワイドベースライン画像マッチング、画像ローカリゼーションベンチマークを顕著なマージンで上回る。
  論文  参考訳（メタデータ） (2021-01-03T09:10:00Z)
• Multi-Agent Reinforcement Learning in Stochastic Networked Systems [30.78949372661673]
  エージェントネットワークにおけるマルチエージェント強化学習(MARL)について検討する。 目的は、世界的報酬を最大化する局所的な政策を見つけることである。
  論文  参考訳（メタデータ） (2020-06-11T16:08:16Z)

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

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