論文の概要: A Fast Graph Neural Network-Based Method for Winner Determination in Multi-Unit Combinatorial Auctions

• arxiv url: http://arxiv.org/abs/2009.13697v2
• Date: Mon, 21 Dec 2020 15:31:41 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-13 05:53:19.934270
• Title: A Fast Graph Neural Network-Based Method for Winner Determination in Multi-Unit Combinatorial Auctions
• Title（参考訳）: 高速グラフニューラルネットワークを用いたマルチユニットコンビネータオークションにおける勝者決定手法
• Authors: Mengyuan Lee, Seyyedali Hosseinalipour, Christopher G. Brinton, Guanding Yu, and Huaiyu Dai
• Abstract要約: オークション(Auction, ACA)は、クラウドコンピューティングを含むさまざまな分野におけるリソース割り当ての効率的なメカニズムである。 競売人の収入を最大化するために入札者間でアイテムを割り当てることの問題は、NP完全で解決不可能である。 本稿では、機械学習(ML)技術を活用して、この問題を解決するための新たな低複雑さアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 44.14410999484577
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The combinatorial auction (CA) is an efficient mechanism for resource allocation in different fields, including cloud computing. It can obtain high economic efficiency and user flexibility by allowing bidders to submit bids for combinations of different items instead of only for individual items. However, the problem of allocating items among the bidders to maximize the auctioneers" revenue, i.e., the winner determination problem (WDP), is NP-complete to solve and inapproximable. Existing works for WDPs are generally based on mathematical optimization techniques and most of them focus on the single-unit WDP, where each item only has one unit. On the contrary, few works consider the multi-unit WDP in which each item may have multiple units. Given that the multi-unit WDP is more complicated but prevalent in cloud computing, we propose leveraging machine learning (ML) techniques to develop a novel low-complexity algorithm for solving this problem with negligible revenue loss. Specifically, we model the multi-unit WDP as an augmented bipartite bid-item graph and use a graph neural network (GNN) with half-convolution operations to learn the probability of each bid belonging to the optimal allocation. To improve the sample generation efficiency and decrease the number of needed labeled instances, we propose two different sample generation processes. We also develop two novel graph-based post-processing algorithms to transform the outputs of the GNN into feasible solutions. Through simulations on both synthetic instances and a specific virtual machine (VM) allocation problem in a cloud computing platform, we validate that our proposed method can approach optimal performance with low complexity and has good generalization ability in terms of problem size and user-type distribution.
• Abstract（参考訳）: コンビネートオークション(英: combinatorial auction, ca)は、クラウドコンピューティングを含む様々な分野における資源配分の効率的なメカニズムである。 入札者が個々の項目のみでなく、異なる項目の組み合わせの入札を行えるようにすることで、高い経済効率とユーザーの柔軟性を得ることができる。 しかし,競売人の収益を最大化するために入札者間でアイテムを割り当てるという問題,すなわち勝者決定問題(WDP)はNP完全であり,不適合である。 WDPの既存の研究は一般に数学的な最適化技術に基づいており、そのほとんどは単一の単位のWDPに焦点を合わせている。 反対に、各アイテムが複数のユニットを持つ可能性があるマルチユニットwdpを考える作品はほとんどない。 マルチユニットWDPはより複雑だがクラウドコンピューティングで広く普及しているため,機械学習(ML)技術を活用して,この問題を解決するための新たな低複雑性アルゴリズムを提案する。 具体的には、マルチユニットWDPを拡張二部入札グラフとしてモデル化し、半畳み込み演算を備えたグラフニューラルネットワークを用いて、最適な割り当てに属する各入札の確率を学習する。 サンプル生成効率の向上とラベル付きインスタンス数の減少を目的として,2つの異なるサンプル生成プロセスを提案する。 また,gnnの出力を実現可能な解に変換する2つのグラフベースポストプロセッシングアルゴリズムを開発した。 クラウドコンピューティングプラットフォームにおける合成インスタンスと特定仮想マシン(VM)割り当て問題の両方をシミュレーションすることにより,提案手法が低複雑性で最適性能に近づき,問題サイズやユーザ型分布の点で優れた一般化能力を有することを示す。

関連論文リスト

• Random Aggregate Beamforming for Over-the-Air Federated Learning in Large-Scale Networks [66.18765335695414]
  本稿では,アグリゲーションエラーを最小限に抑え,選択したデバイス数を最大化する目的で,共同装置の選択とアグリゲーションビームフォーミング設計について検討する。 コスト効率のよい方法でこの問題に取り組むために,ランダムな集合ビームフォーミング方式を提案する。 また, 得られた集計誤差と, デバイス数が大きい場合に選択したデバイス数についても解析を行った。
  論文  参考訳（メタデータ） (2024-02-20T23:59:45Z)
• A Multi-Head Ensemble Multi-Task Learning Approach for Dynamical Computation Offloading [62.34538208323411]
  共有バックボーンと複数の予測ヘッド(PH)を組み合わせたマルチヘッドマルチタスク学習(MEMTL)手法を提案する。 MEMTLは、追加のトレーニングデータを必要とせず、推測精度と平均平方誤差の両方でベンチマーク手法より優れている。
  論文  参考訳（メタデータ） (2023-09-02T11:01:16Z)
• Federated K-Means Clustering via Dual Decomposition-based Distributed Optimization [0.0]
  本稿では,$Kのクラスタリング問題に対する分散トレーニングに双対分解を適用する方法について述べる。 トレーニングは、異なるノードにデータを分割し、コンセンサス制約を通じてこれらのノードをリンクすることで、分散的に行うことができる。
  論文  参考訳（メタデータ） (2023-07-25T05:34:50Z)
• End-to-End Pareto Set Prediction with Graph Neural Networks for Multi-objective Facility Location [10.130342722193204]
  施設配置問題(FLP)は、サプライチェーンやロジスティクスで広く見られるNPハード最適化問題の典型的なクラスである。 本稿では,システム全体のコストを同時に最小化し,システム信頼性を最大化する多目的施設配置問題(MO-FLP)について考察する。 ノードとエッジの暗黙グラフ表現を学習するために、2つのグラフニューラルネットワークを構築した。
  論文  参考訳（メタデータ） (2022-10-27T07:15:55Z)
• Task-Oriented Sensing, Computation, and Communication Integration for Multi-Device Edge AI [108.08079323459822]
  本稿では,AIモデルの分割推論と統合センシング通信(ISAC)を併用した,新しいマルチインテリジェントエッジ人工レイテンシ(AI)システムについて検討する。 推定精度は近似的だが抽出可能な計量、すなわち判別利得を用いて測定する。
  論文  参考訳（メタデータ） (2022-07-03T06:57:07Z)
• API: Boosting Multi-Agent Reinforcement Learning via Agent-Permutation-Invariant Networks [35.63476630248861]
  多エージェント強化学習は、状態-作用空間の指数的な成長によりサンプル効率が低下する。 置換不変量(PI)を実現するための2つの新しい設計を提案する。 最初の設計は、同じが異なる順序の入力を同じ順序に戻し、下流ネットワークは、固定順序の入力よりも関数マッピングを学ぶ必要がある。
  論文  参考訳（メタデータ） (2022-03-10T11:00:53Z)
• A multi-domain VNE algorithm based on multi-objective optimization for IoD architecture in Industry 4.0 [10.110571882165997]
  Internet of Drones (IoD) の開発により、UAVの運用はより自律的になる。 潜在的資源を合理的に割り当てる方法は、解決すべき緊急の問題となっている。
  論文  参考訳（メタデータ） (2022-02-08T07:56:28Z)
• Solving Mixed Integer Programs Using Neural Networks [57.683491412480635]
  本稿では,mipソルバの2つのキーサブタスクに学習を適用し,高品質なジョイント変数割当を生成し,その割当と最適課題との客観的値の差を限定する。 提案手法は,ニューラルネットワークに基づく2つのコンポーネントであるニューラルダイバーディングとニューラルブランチを構築し,SCIPなどのベースMIPソルバで使用する。 2つのGoogle生産データセットとMIPLIBを含む6つの現実世界データセットに対するアプローチを評価し、それぞれに別々のニューラルネットワークをトレーニングする。
  論文  参考訳（メタデータ） (2020-12-23T09:33:11Z)
• The Best of Many Worlds: Dual Mirror Descent for Online Allocation Problems [7.433931244705934]
  本稿では,意思決定者に対して未知の入力モデルを用いて,各要求に対する報酬とリソース消費を生成するデータ駆動型設定について考察する。 様々な入力モデルにおいて,どの入力に直面するかを知ることなく,優れた性能が得られるアルゴリズムの一般クラスを設計する。 我々のアルゴリズムはラグランジアン双対空間で動作し、オンラインミラー降下を用いて更新される各リソースに対して双対乗算器を保持する。
  論文  参考訳（メタデータ） (2020-11-18T18:39:17Z)
• Coded Stochastic ADMM for Decentralized Consensus Optimization with Edge Computing [113.52575069030192]
  セキュリティ要件の高いアプリケーションを含むビッグデータは、モバイルデバイスやドローン、車両など、複数の異種デバイスに収集され、格納されることが多い。 通信コストとセキュリティ要件の制限のため、核融合センターにデータを集約するのではなく、分散的に情報を抽出することが最重要となる。 分散エッジノードを介してデータを局所的に処理するマルチエージェントシステムにおいて,モデルパラメータを学習する問題を考える。 分散学習モデルを開発するために,乗算器アルゴリズムの最小バッチ交互方向法(ADMM)のクラスについて検討した。
  論文  参考訳（メタデータ） (2020-10-02T10:41:59Z)

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

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