Online Task Assignment Problems with Reusable Resources

Hanna Sumita, Shinji Ito, Kei Takemura, Daisuke Hatano, Takuro Fukunaga, Naonori Kakimura, Ken Ichi Kawarabayashi

研究成果: Conference contribution

7 被引用数 (Scopus)

抄録

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 ∆ times, the algorithm is shown to have the competitive ratio ∆/(3∆ − 1) ≥ 1/3. We also evaluate our proposed algorithm with numerical experiments.

本文言語English
ホスト出版物のタイトルAAAI-22 Technical Tracks 5
出版社Association for the Advancement of Artificial Intelligence
ページ5199-5207
ページ数9
ISBN(電子版)1577358767, 9781577358763
出版ステータスPublished - 2022 6月 30
イベント36th AAAI Conference on Artificial Intelligence, AAAI 2022 - Virtual, Online
継続期間: 2022 2月 222022 3月 1

出版物シリーズ

名前Proceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022
36

Conference

Conference36th AAAI Conference on Artificial Intelligence, AAAI 2022
CityVirtual, Online
Period22/2/2222/3/1

ASJC Scopus subject areas

  • 人工知能

フィンガープリント

「Online Task Assignment Problems with Reusable Resources」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。

引用スタイル