論文の概要: Sublinear Time Algorithm for Online Weighted Bipartite Matching
- arxiv url: http://arxiv.org/abs/2208.03367v2
- Date: Mon, 12 Feb 2024 14:20:41 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-14 01:41:33.246711
- Title: Sublinear Time Algorithm for Online Weighted Bipartite Matching
- Title（参考訳）: オンライン重み付きバイパートイトマッチングのためのサブ線形時間アルゴリズム
- Authors: Hang Hu, Zhao Song, Runzhou Tao, Zhaozhuo Xu, Junze Yin, Danyang Zhuo
- Abstract要約: オンラインバイパーティイトマッチングは、オンラインアルゴリズムの基本的な問題である。
ウェイトは、ユーザのディープ表現とアイテムのディープ表現との間の内部積によって決定される。
提案したランダム化データ構造では,マッチングアルゴリズムの競合比を保ちながら,重みをサブ線形時間で計算できることが示されている。
- 参考スコア（独自算出の注目度）: 16.48305467237292
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Online bipartite matching is a fundamental problem in online algorithms. The
goal is to match two sets of vertices to maximize the sum of the edge weights,
where for one set of vertices, each vertex and its corresponding edge weights
appear in a sequence. Currently, in the practical recommendation system or
search engine, the weights are decided by the inner product between the deep
representation of a user and the deep representation of an item. The standard
online matching needs to pay $nd$ time to linear scan all the $n$ items,
computing weight (assuming each representation vector has length $d$), and then
deciding the matching based on the weights. However, in reality, the $n$ could
be very large, e.g. in online e-commerce platforms. Thus, improving the time of
computing weights is a problem of practical significance. In this work, we
provide the theoretical foundation for computing the weights approximately. We
show that, with our proposed randomized data structures, the weights can be
computed in sublinear time while still preserving the competitive ratio of the
matching algorithm.
- Abstract（参考訳）: オンラインバイパーティイトマッチングは、オンラインアルゴリズムの基本的な問題である。
目標は、辺重みの和を最大化するために2組の頂点を一致させることであり、1組の頂点に対して、それぞれの頂点とその対応する辺重みが列に現れる。
現在、実用的なレコメンデーションシステムや検索エンジンでは、ユーザの深い表現とアイテムの深い表現との間の内積によって重み付けが決定される。
標準オンラインマッチングは、すべてのn$アイテムをリニアスキャンするためにnd$時間を支払う必要があり、(各表現ベクトルが長さ$d$と仮定して)重みを計算し、その重みに基づいてマッチングを決定する。
しかし、実際に$n$は、例えばオンラインeコマースプラットフォームにおいて非常に大きなものになり得る。
したがって、重みの計算時間を改善することは実用上重要な問題である。
本研究では,重みを近似的に計算する理論的基礎を提供する。
提案したランダム化データ構造では,マッチングアルゴリズムの競合比を保ちながら,重みをサブ線形時間で計算できることが示されている。
関連論文リスト
- Pushing the Limits: Concurrency Detection in Acyclic Sound Free-Choice Workflow Nets in $O(P^2 + T^2)$ [0.8192907805418583]
どの場所とトランジションを並列に実行できるかを知ることは、計算ネットを理解するのに役立つ。
Kovalyov と Esparza は、Obig((P+T)TP2big)$ のすべての並列な場所をライブおよび有界ネットで計算するアルゴリズムを開発した。
本稿では,検出アルゴリズムのパレットとコンカレントパス(CP)アルゴリズムを補完する。
論文 参考訳（メタデータ） (2024-01-29T12:11:34Z) - Scalable network reconstruction in subquadratic time [0.0]
本稿では,この2次ベースラインを大幅に上回る広範囲の再構成問題に適用可能な一般アルゴリズムを提案する。
我々のアルゴリズムは、高い確率で最適なエッジ候補を生成する第2の隣人探索に依存している。
本アルゴリズムは2次ベースラインよりも桁違いに高速な性能を実現する。
論文 参考訳（メタデータ） (2024-01-02T19:00:13Z) - Equivariant Deep Weight Space Alignment [54.65847470115314]
本稿では,ウェイトアライメント問題を解決するための学習を目的とした新しいフレームワークを提案する。
まず、重み調整が2つの基本対称性に一致することを証明し、それからこれらの対称性を尊重する深いアーキテクチャを提案する。
論文 参考訳（メタデータ） (2023-10-20T10:12:06Z) - Computing Star Discrepancies with Numerical Black-Box Optimization
Algorithms [56.08144272945755]
我々は,L_infty$星差分問題に対する8つの一般的な数値ブラックボックス最適化アルゴリズムを比較した。
使用済みのソルバは、ほとんどのケースで非常にひどいパフォーマンスを示します。
我々は、最先端の数値ブラックボックス最適化手法が問題のグローバルな構造を捉えるのに失敗していると疑っている。
論文 参考訳（メタデータ） (2023-06-29T14:57:56Z) - CCuantuMM: Cycle-Consistent Quantum-Hybrid Matching of Multiple Shapes [62.45415756883437]
多重非剛性な3次元形状の整合性は困難で、$mathcalNP$-hard問題である。
既存の量子形状マッチング法は複数の形状をサポートしておらず、サイクルの整合性も低い。
本稿では,3次元形状のマルチマッチングのための最初の量子ハイブリッド手法を提案する。
論文 参考訳（メタデータ） (2023-03-28T17:59:55Z) - An Improved Algorithm For Online Min-Sum Set Cover [0.45687771576879593]
我々は、アルゴリズムが注文された$n$要素のリストを保持するオンライン嗜好集約のモデルについて研究する。
競合比(ALG-to-OPTコスト比)が$O(r2)$である計算効率の良いランダム化アルゴリズムを構築する。
O(r3/2 cdot sqrtn)$-competitive and $Omega(r)$ is a lower bound on the performance of any deterministic online algorithm。
論文 参考訳（メタデータ） (2022-09-11T14:03:51Z) - A Scalable Combinatorial Solver for Elastic Geometrically Consistent 3D
Shape Matching [69.14632473279651]
本稿では,3次元形状間の幾何学的一貫したマッピング空間をグローバルに最適化するスケーラブルなアルゴリズムを提案する。
従来の解法よりも数桁高速なラグランジュ双対問題と結合した新しい原始問題を提案する。
論文 参考訳（メタデータ） (2022-04-27T09:47:47Z) - Deep Policies for Online Bipartite Matching: A Reinforcement Learning
Approach [5.683591363967851]
本稿では,過去のデータに対する試行錯誤に基づく適切な対応策を導出するためのエンドツーエンド強化学習フレームワークを提案する。
学習手法の大部分は,4つの合成および実世界のデータセットにおいて,古典的なグリーディアルゴリズムよりもはるかに優れていることを示す。
論文 参考訳（メタデータ） (2021-09-21T18:04:19Z) - Metrical Task Systems with Online Machine Learned Advice [0.0]
機械学習予測器によるオンラインアルゴリズムの強化は,予測器の精度が適切であれば,競争比を確実に低下させることができることを示す。
我々は、$n$タスク上の一様タスクシステムの特定のクラスに焦点を当て、最良の決定論的アルゴリズムは$O(n)$競争であり、最良のランダム化アルゴリズムは$O(log n)$競争である。
論文 参考訳（メタデータ） (2020-12-17T04:56:51Z) - 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) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳（メタデータ） (2020-02-26T16:19:09Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。