Submodular reassignment problem for reallocating agents to tasks with synergy effects

Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto

研究成果: Article査読


We propose a new combinatorial optimization problem that we call the submodular reassignment problem. We are given k submodular functions over the same ground set, and we want to find a set that minimizes the sum of the distances to the sets of minimizers of all functions. The problem is motivated by a two-stage stochastic optimization problem with recourse summarized as follows. We are given two tasks to be processed and want to assign a set of workers to maximize the sum of profits. However, we do not know the value functions exactly, but only know a finite number of possible scenarios. Our goal is to determine the first-stage allocation of workers to minimize the expected number of reallocated workers after a scenario is realized at the second stage. This problem can be modeled by the submodular reassignment problem. We prove that the submodular reassignment problem can be solved in strongly polynomial time via submodular function minimization. We further provide a maximum-flow formulation of the problem that enables us to solve the problem without using a general submodular function minimization algorithm, and more efficiently both in theory and in practice. In our algorithm, we make use of Birkhoff's representation theorem for distributive lattices.

ジャーナルDiscrete Optimization
出版ステータスPublished - 2022 5月

ASJC Scopus subject areas

  • 理論的コンピュータサイエンス
  • 計算理論と計算数学
  • 応用数学


「Submodular reassignment problem for reallocating agents to tasks with synergy effects」の研究トピックを掘り下げます。これらがまとまってユニークなフィンガープリントを構成します。