Submodular Reassignment Problem for Reallocating Agents to Tasks with Synergy Effects
Submodular Reassignment Problem for Reallocating Agents to Tasks with Synergy Effects
复制标题
将代理重新分配给具有协同效应的任务的子模块重新分配问题
DOI：
10.1016/j.disopt.2021.100631
复制
发表时间：
2021
影响因子：
1.1
通讯作者：
and Yoshio Okamoto
中科院分区：
文献类型：
--
作者：
Naonori Kakimura;Naoyuki Kamiyama;Yusuke Kobayashi;and Yoshio Okamoto
我们提出了一个新的组合优化问题，我们称之为子模块重新分配问题。我们在同一个基集上给定k个次模函数，我们希望找到一个集，使所有函数到极小化集的距离之和最小化。该问题的动机是一个两阶段的随机优化问题的追索权总结如下。我们有两个任务要处理，并希望分配一组工人以最大化利润之和。然而，我们并不确切地知道价值函数，而只知道有限数量的可能情况。我们的目标是确定第一阶段的工人分配，以尽量减少预期的重新分配的工人数量后，在第二阶段实现的情况。这个问题可以用子模块再分配问题来建模。我们证明了次模再分配问题可以通过次模函数极小化在强多项式时间内求解。我们进一步提供了一个最大流的问题，使我们能够解决这个问题，而不使用一般的次模函数最小化算法，更有效地在理论和实践中。在我们的算法中，我们利用分配格的Birkhoff表示定理。
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.