TY - JOUR

T1 - Submodular reassignment problem for reallocating agents to tasks with synergy effects

AU - Kakimura, Naonori

AU - Kamiyama, Naoyuki

AU - Kobayashi, Yusuke

AU - Okamoto, Yoshio

N1 - Funding Information:
Partly supported by JSPS, Japan KAKENHI Grant Nos. JP17K00028, JP18H05291, JP20K21834 and JP20H05795, Japan.Partially supported by JST PRESTO, Japan Grant No. JPMJPR1753, Japan.Partly supported by JSPS, Japan KAKENHI Grant Nos. JP18H05291, JP19H05485, JP20K11692, and JP20H05795, Japan.Partially supported by JSPS, Japan KAKENHI Grant Nos. JP15K00009, JP20K11670, JP20H05795, JST, Japan CREST Grant No. JPMJCR1402, and Kayamori Foundation of Informational Science Advancement.
Publisher Copyright:
© 2021 Elsevier B.V.

PY - 2022/5

Y1 - 2022/5

N2 - 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.

AB - 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.

KW - Birkhoff's representation theorem

KW - Distributive lattice

KW - Minimum cut

KW - Stochastic optimization

KW - Submodular function

UR - http://www.scopus.com/inward/record.url?scp=85101697319&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85101697319&partnerID=8YFLogxK

U2 - 10.1016/j.disopt.2021.100631

DO - 10.1016/j.disopt.2021.100631

M3 - Article

AN - SCOPUS:85101697319

SN - 1572-5286

VL - 44

JO - Discrete Optimization

JF - Discrete Optimization

M1 - 100631

ER -