論文の概要: Learning-Augmented Online Bipartite Matching in the Random Arrival Order Model

• arxiv url: http://arxiv.org/abs/2511.23388v1
• Date: Fri, 28 Nov 2025 17:31:11 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-12-01 19:47:56.001245
• Title: Learning-Augmented Online Bipartite Matching in the Random Arrival Order Model
• Title（参考訳）: ランダム順序モデルにおける学習強化オンライン二部マッチング
• Authors: Kunanon Burathep, Thomas Erlebach, William K. Moses,
• Abstract要約: ランダム到着順序モデルにおけるオンライン非重み付き二部マッチング問題について検討する。 我々の学習強化アルゴリズムは、1-o(1))$-consistencyと$(-o(1))$-robustnessを達成する。
• 参考スコア（独自算出の注目度）: 0.688204255655161
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the online unweighted bipartite matching problem in the random arrival order model, with $n$ offline and $n$ online vertices, in the learning-augmented setting: The algorithm is provided with untrusted predictions of the types (neighborhoods) of the online vertices. We build upon the work of Choo et al. (ICML 2024, pp. 8762-8781) who proposed an approach that uses a prefix of the arrival sequence as a sample to determine whether the predictions are close to the true arrival sequence and then either follows the predictions or uses a known baseline algorithm that ignores the predictions and is $β$-competitive. Their analysis is limited to the case that the optimal matching has size $n$, i.e., every online vertex can be matched. We generalize their approach and analysis by removing any assumptions on the size of the optimal matching while only requiring that the size of the predicted matching is at least $αn$ for any constant $0 < α\le 1$. Our learning-augmented algorithm achieves $(1-o(1))$-consistency and $(β-o(1))$-robustness. Additionally, we show that the competitive ratio degrades smoothly between consistency and robustness with increasing prediction error.
• Abstract（参考訳）: ランダム到着順序モデルにおけるオンライン非重み付き二分項マッチング問題について,オンライン頂点のタイプ(周辺)の信頼できない予測を学習補助条件として,$n$オフラインおよび$n$オンライン頂点を用いて検討した。 我々は、Choo et al (ICML 2024, pp. 8762-8781) の業績に基づいて、到着シーケンスのプレフィックスをサンプルとして、予測が真の到着シーケンスに近いかどうかを判断し、予測に従うか、予測を無視してβ$-competitive(英語版)という既知のベースラインアルゴリズムを使用するアプローチを提案する。 彼らの分析は、最適マッチングが$n$である場合、すなわち、全てのオンライン頂点が一致できる場合に限られる。 最適マッチングのサイズに関する仮定を取り除き、予測マッチングのサイズが任意の定数$0 < α\le 1$に対して少なくとも$αn$であることを要求することで、それらのアプローチと解析を一般化する。 学習強化アルゴリズムは1-o(1))$-consistencyと$(β-o(1))$-robustnessを達成する。 さらに、競合比は、予測誤差の増加とともに、一貫性とロバスト性の間に滑らかに低下することを示す。

関連論文リスト

• Multicalibration yields better matchings [18.479215073073693]
  不完全な予測器が与えられた場合、最適下決定規則は誘導された誤りを補うことができ、したがって標準最適規則よりも優れる。 以下のプロパティで、特定のマルチキャリブレーションされた予測子$hat $を構築する方法を示す。 hat $の出力に基づいて最適なマッチングを選択することは、オリジナルの予測子に適用された$mathcal C$の最良の決定ルールと競合する。
  論文  参考訳（メタデータ） (2025-11-14T15:45:07Z)
• Provable Scaling Laws for the Test-Time Compute of Large Language Models [84.00141420901038]
  本研究では,大規模言語モデルのテスト時間計算において,証明可能なスケーリング法則を享受する2つのアルゴリズムを提案する。 1つは2段階ノックアウト方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。 もう1つは2段階のリーグ方式のアルゴリズムで、各候補は複数の相手に対して平均勝利率で評価される。
  論文  参考訳（メタデータ） (2024-11-29T05:29:47Z)
• Competitive strategies to use "warm start" algorithms with predictions [12.970501425097645]
  本稿では,温暖化開始アルゴリズムの学習と予測利用の問題点について考察する。 この設定では、アルゴリズムは問題のインスタンスと解の予測を与える。 我々は、$k$の予測を考慮に入れたより強力なベンチマークに対して、競争力のある保証を与えます。
  論文  参考訳（メタデータ） (2024-05-06T17:38:20Z)
• Mixing predictions for online metric algorithms [34.849039387367455]
  我々は予測を組み合わせるアルゴリズムを設計し、このような動的組み合わせと競合する。 我々のアルゴリズムは、バンディットのような方法で予測者にアクセスするように適応することができ、一度に1つの予測者しかクエリできない。 我々の下界の1つが予想外の意味を持つのは、$k$-server問題に対する定式化のカバーに関する新しい構造的洞察である。
  論文  参考訳（メタデータ） (2023-04-04T13:18:00Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  階層クラスタリングのための微分プライベート近似アルゴリズムについて検討する。 例えば、$epsilon$-DPアルゴリズムは入力データセットに対して$O(|V|2/epsilon)$-additiveエラーを示さなければならない。 本稿では,ブロックを正確に復元する1+o(1)$近似アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-31T19:14:30Z)
• Learning-Augmented Algorithms for Online TSP on the Line [4.636538620253008]
  本研究では,オンライントラベリングセールスマン問題 (TSP) を,機械学習による予測を付加した線上で研究する。 古典的な問題では、実際の行に沿って時間をかけてリリースされるリクエストのストリームがあります。 オープンな変種とクローズドな変種を区別し、全ての要求を処理した後、アルゴリズムに元の値を返すように要求する。
  論文  参考訳（メタデータ） (2022-06-01T17:47:26Z)
• Deep Probabilistic Graph Matching [72.6690550634166]
  本稿では,マッチング制約を伴わずに,元のQAPに適合する深層学習ベースのグラフマッチングフレームワークを提案する。 提案手法は,一般的な3つのベンチマーク(Pascal VOC,Wilow Object,SPair-71k)で評価され,すべてのベンチマークにおいて過去の最先端よりも優れていた。
  論文  参考訳（メタデータ） (2022-01-05T13:37:27Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)
• Ranking a set of objects: a graph based least-square approach [70.7866286425868]
  同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。 品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
  論文  参考訳（メタデータ） (2020-02-26T16:19:09Z)

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

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