On Submodular Search and Machine Scheduling
On Submodular Search and Machine Scheduling
复制标题
DOI：
10.1287/moor.2018.0978
复制
发表时间：
2016-07
期刊：
影响因子：
--
通讯作者：
R. Fokkink;T. Lidbetter;L. V'egh
中科院分区：
文献类型：
--
作者：
R. Fokkink;T. Lidbetter;L. V'egh
假设一些对象隐藏在有限的隐藏位置集合 S 中，必须逐个检查这些隐藏位置。搜索 S 子集的成本由子模函数给出，所有对象都包含在子集中的概率由超模函数给出。我们寻求 S 的排序，以最小的预期成本找到所有对象。这个问题是 NP 困难的，我们给出了一种有效的组合 2 逼近算法，推广了调度理论中的类似结果。我们还给出了一种新的调度应用程序，其中一组作业必须按照优先级约束进行排序，以最小化作业子集完成时间的某些凹函数的加权和。我们继续为具有低总曲率的子模函数提供更好的近似，并且当问题是我们所说的串并联可分解时，我们给出完整的解决方案。接下来，我们考虑成本最大化隐藏者和成本最小化搜索者之间的零和博弈。我们证明了隐藏者的均衡混合策略位于成本函数的基本多面体中，并进行了适当缩放，并且我们在串联并行可分解情况下解决了博弈，在其他情况下给出了近似最优策略。
Suppose that some objects are hidden in a finite set S of hiding places that must be examined one by one. The cost of searching subsets of S is given by a submodular function, and the probability that all objects are contained in a subset is given by a supermodular function. We seek an ordering of S that finds all the objects with minimal expected cost. This problem is NP-hard, and we give an efficient combinatorial 2-approximation algorithm, generalizing analogous results in scheduling theory. We also give a new scheduling application where a set of jobs must be ordered subject to precedence constraints to minimize the weighted sum of some concave function of the completion times of subsets of jobs. We go on to give better approximations for submodular functions with low total curvature, and we give a full solution when the problem is what we call series-parallel decomposable. Next, we consider a zero-sum game between a cost-maximizing hider and a cost-minimizing searcher. We prove that the equilibrium mixed strategies for the hider are in the base polyhedron of the cost function, suitably scaled, and we solve the game in the series-parallel decomposable case, giving approximately optimal strategies in other cases.