論文の概要: Online Task Assignment Problems with Reusable Resources

• arxiv url: http://arxiv.org/abs/2203.07605v1
• Date: Tue, 15 Mar 2022 02:48:13 GMT
• ステータス: 処理完了
• システム内更新日: 2022-03-16 15:45:10.789119
• Title: Online Task Assignment Problems with Reusable Resources
• Title（参考訳）: 再利用可能な資源を用いたオンラインタスク割り当て問題
• Authors: Hanna Sumita, Shinji Ito, Kei Takemura, Daisuke Hatano, Takuro Fukunaga, Naonori Kakimura, Ken-ichi Kawarabayashi
• Abstract要約: 再利用可能な資源を用いたオンラインタスク割り当て問題について検討する。 本稿では,この設定に対して1/2$-competitiveのオンラインアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 44.87346665037376
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study online task assignment problem with reusable resources, motivated by practical applications such as ridesharing, crowdsourcing and job hiring. In the problem, we are given a set of offline vertices (agents), and, at each time, an online vertex (task) arrives randomly according to a known time-dependent distribution. Upon arrival, we assign the task to agents immediately and irrevocably. The goal of the problem is to maximize the expected total profit produced by completed tasks. The key features of our problem are (1) an agent is reusable, i.e., an agent comes back to the market after completing the assigned task, (2) an agent may reject the assigned task to stay the market, and (3) a task may accommodate multiple agents. The setting generalizes that of existing work in which an online task is assigned to one agent under (1). In this paper, we propose an online algorithm that is $1/2$-competitive for the above setting, which is tight. Moreover, when each agent can reject assigned tasks at most $\Delta$ times, the algorithm is shown to have the competitive ratio $\Delta/(3\Delta-1)\geq 1/3$. We also evaluate our proposed algorithm with numerical experiments.
• Abstract（参考訳）: 本研究では,ライドシェアリング,クラウドソーシング,求人といった実践的な応用を動機とした,再利用可能な資源を用いたオンラインタスク割り当て問題について検討する。 この問題では、オフライン頂点(エージェント)のセットが与えられ、オンライン頂点(タスク)が既知の時間依存分布に従ってランダムに到着する。 到着後、我々はその任務を直ちに、そして無断でエージェントに割り当てる。 課題の目標は、完了したタスクが生み出す総利益を最大化することである。 本問題の主な特徴は,(1)エージェントが再利用可能なこと,(2)エージェントが割り当てられたタスクを完了した後に市場に戻ってくること,(2)エージェントがマーケットに留まるために割り当てられたタスクを拒絶すること,(3)タスクが複数のエージェントに対応できること,である。 オンラインタスクが(1)の下に1つのエージェントに割り当てられた既存の作業の作業を一般化する。 本稿では,上記の設定に対して1/2$の競合性を持つオンラインアルゴリズムを提案する。 さらに、各エージェントが割り当てられたタスクを最大$\Delta$で拒否できる場合、アルゴリズムは競争率$\Delta/(3\Delta-1)\geq 1/3$を持つ。 また,提案アルゴリズムを数値実験により評価する。

関連論文リスト

• A Dynamic LLM-Powered Agent Network for Task-Oriented Agent Collaboration [55.35849138235116]
  本稿では,様々なタスクやドメインに対する動的コミュニケーション構造において,候補からエージェントのチームを自動的に選択する手法を提案する。 具体的には, LLMを利用したエージェント協調のための動的LLMパワーエージェントネットワーク(textDyLAN$)というフレームワークを構築した。 我々は、コード生成、意思決定、一般的な推論、算術的推論タスクにおいて、適度な計算コストで、DyLANが強力なベースラインを上回ることを実証する。
  論文  参考訳（メタデータ） (2023-10-03T16:05:48Z)
• Active Ranking of Experts Based on their Performances in Many Tasks [72.96112117037465]
  我々は、dタスクのパフォーマンスに基づいて、n名のエキスパートをランク付けする問題を考察する。 我々は,各専門家のペアに対して,各タスクにおいて他方よりも優れているという,単調な仮定を定めている。
  論文  参考訳（メタデータ） (2023-06-05T06:55:39Z)
• Robust Subtask Learning for Compositional Generalization [20.54144051436337]
  我々は、どんなタスクでも実行できるように、サブタスクポリシーをトレーニングする問題に焦点を合わせます。 我々は、平均的なケースのパフォーマンスとは対照的に、すべてのタスクで最悪のケースのパフォーマンスを最大化することを目指している。
  論文  参考訳（メタデータ） (2023-02-06T18:19:25Z)
• Multi-Agent Neural Rewriter for Vehicle Routing with Limited Disclosure of Costs [65.23158435596518]
  チームのマルコフゲームとして、部分的に観測可能なコストでマルチサイクルルーティング問題を解く。 我々のマルチエージェント強化学習アプローチである、いわゆるマルチエージェントニューラルリライタは、1エージェントニューラルリライタを利用して、反復的に書き換えるソリューションによって問題を解決する。
  論文  参考訳（メタデータ） (2022-06-13T09:17:40Z)
• On the Expressivity of Markov Reward [89.96685777114456]
  本稿では,エージェントが実行するタスクをキャプチャする手段として,報酬の表現性を理解することを目的としている。 本研究は,(1)許容される行動の集合,(2)行動上の部分順序,(3)軌道上の部分順序の3つの新しい抽象概念「タスク」について考察する。
  論文  参考訳（メタデータ） (2021-11-01T12:12:16Z)
• Polynomial-Time Algorithms for Multi-Agent Minimal-Capacity Planning [19.614913673879474]
  共有タスクを達成するために協力する自律エージェントのリソース容量を最小化する問題を研究する。 消費マルコフ決定過程において、エージェントは限られた容量の資源を有する。 我々は,このグラフ問題をエージェント数,ターゲット位置,消費マルコフ決定過程の大きさで時間的に解くアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2021-05-04T00:30:02Z)
• Multi-Agent Routing and Scheduling Through Coalition Formation [13.302347777866757]
  この問題をマルチエージェントルーティングと協調形成(marsc)によるスケジューリングと呼ぶ。 私たちは、Time Windowsで重要なチームオリエンテーション問題を一般化していることを示しています。 リアルタイムシステムで一般的に使用されるEarliest Deadline Firstアプローチよりも最大3.25倍優れたソリューションを見つけます。
  論文  参考訳（メタデータ） (2021-05-02T11:53:44Z)
• Dynamic Multi-Robot Task Allocation under Uncertainty and Temporal Constraints [52.58352707495122]
  本稿では,不確実性およびマルチエージェント協調の下での逐次意思決定における重要な計算課題を分離するマルチロボット割当アルゴリズムを提案する。 都市におけるマルチアームコンベヤベルトピック・アンド・プレイスとマルチドローン配送ディスパッチの2つの異なる領域における広範囲なシミュレーション結果について検証を行った。
  論文  参考訳（メタデータ） (2020-05-27T01:10:41Z)

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

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