Online Task Assignment Problems with Reusable Resources

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

7 Citations (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.

Original languageEnglish
Title of host publicationAAAI-22 Technical Tracks 5
PublisherAssociation for the Advancement of Artificial Intelligence
Number of pages9
ISBN (Electronic)1577358767, 9781577358763
Publication statusPublished - 2022 Jun 30
Event36th AAAI Conference on Artificial Intelligence, AAAI 2022 - Virtual, Online
Duration: 2022 Feb 222022 Mar 1

Publication series

NameProceedings of the 36th AAAI Conference on Artificial Intelligence, AAAI 2022


Conference36th AAAI Conference on Artificial Intelligence, AAAI 2022
CityVirtual, Online

ASJC Scopus subject areas

  • Artificial Intelligence


Dive into the research topics of 'Online Task Assignment Problems with Reusable Resources'. Together they form a unique fingerprint.

Cite this