論文の概要: Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising

• arxiv url: http://arxiv.org/abs/2005.04355v2
• Date: Tue, 12 May 2020 07:37:56 GMT
• ステータス: 処理完了
• システム内更新日: 2022-12-05 07:09:23.939334
• Title: Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising
• Title（参考訳）: オンライン広告における大規模重み付きbマッチング問題に対するヒューリスティック探索の高速化
• Authors: Xiaotian Hao, Junqi Jin, Jianye Hao, Jin Li, Weixun Wang, Yi Ma, Zhenzhe Zheng, Han Li, Jian Xu and Kun Gai
• Abstract要約: バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
• 参考スコア（独自算出の注目度）: 51.97494906131859
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. These practical problems usually exhibit two distinct features: large-scale and dynamic, which requires the matching algorithm to be repeatedly executed at regular intervals. However, existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. To address this issue, we propose \texttt{NeuSearcher} which leverages the knowledge learned from previously instances to solve new problem instances. Specifically, we design a multichannel graph neural network to predict the threshold of the matched edges weights, by which the search region could be significantly reduced. We further propose a parallel heuristic search algorithm to iteratively improve the solution quality until convergence. Experiments on both open and industrial datasets demonstrate that \texttt{NeuSearcher} can speed up 2 to 3 times while achieving exactly the same matching solution compared with the state-of-the-art approximation approaches.
• Abstract（参考訳）: bマッチングはアルゴリズム設計において基本であり、経済市場や労働市場などに広く適用されている。 これらの実用的な問題は、通常2つの異なる特徴を示す:大規模と動的であり、マッチングアルゴリズムを定期的に繰り返し実行する必要がある。 しかし、既存の完全で近似的なアルゴリズムは、通常、耐え難い実行時間を必要とするか、計算資源が多すぎるため、このような設定では失敗する。 この問題に対処するために,前回のインスタンスから学んだ知識を活用して新しい問題インスタンスを解く, \texttt{neusearcher} を提案する。 具体的には,マッチングエッジ重みのしきい値を予測するために,探索領域を大幅に削減できるマルチチャネルグラフニューラルネットワークを設計した。 さらに,収束まで解の質を反復的に向上させる並列ヒューリスティック探索アルゴリズムを提案する。 オープンデータセットとインダストリアルデータセットの両方の実験により、 \texttt{neusearcher} は2倍から3倍のスピードアップが可能で、最先端の近似アプローチと全く同じソリューションを実現している。

関連論文リスト

• Scalable network reconstruction in subquadratic time [0.0]
  本稿では,この2次ベースラインを大幅に上回る広範囲の再構成問題に適用可能な一般アルゴリズムを提案する。 我々のアルゴリズムは、高い確率で最適なエッジ候補を生成する第2の隣人探索に依存している。 本アルゴリズムは2次ベースラインよりも桁違いに高速な性能を実現する。
  論文  参考訳（メタデータ） (2024-01-02T19:00:13Z)
• Faster Matchings via Learned Duals [31.61057940283721]
  機械学習予測のアイデアと「スタート・ウォーム」原始二元アルゴリズムのアイデアを組み合わせる。 まず、予測可能な双対は実現不可能である可能性があるので、予測できない双対を近くの実現可能な解に効率的にマッピングするアルゴリズムを提供する。 第二に、一度双対が実現可能ならば、それらは最適ではないかもしれない。
  論文  参考訳（メタデータ） (2021-07-20T21:11:09Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Resource Allocation in Multi-armed Bandit Exploration: Overcoming Sublinear Scaling with Adaptive Parallelism [107.48538091418412]
  腕の引っ張りに様々な量の資源を割り当てることができる分割可能な資源にアクセス可能な場合,マルチアームの帯状地における探索について検討する。 特に、分散コンピューティングリソースの割り当てに重点を置いており、プル毎により多くのリソースを割り当てることで、結果をより早く得ることができます。
  論文  参考訳（メタデータ） (2020-10-31T18:19:29Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• SONIA: A Symmetric Blockwise Truncated Optimization Algorithm [2.9923891863939938]
  本研究は, 経験的リスクに対する新しいアルゴリズムを提案する。 このアルゴリズムは、一部分空間における二階探索型更新を計算し、1階探索法と2階探索法の間のギャップを埋める。
  論文  参考訳（メタデータ） (2020-06-06T19:28:14Z)

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

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