Migration as Submodular Optimization
Migration as Submodular Optimization
复制标题
DOI：
10.1609/aaai.v33i01.3301549
复制
发表时间：
2018-09
期刊：
影响因子：
--
通讯作者：
Paul Gölz;Ariel D. Procaccia
中科院分区：
文献类型：
--
作者：
Paul Gölz;Ariel D. Procaccia
移徙带来了广泛的社会挑战，最近引起了科学界的极大关注。有人提出的一个突出的方法是利用优化和机器学习将移民与当地相匹配，以最大限度地提高预期就业的移民人数。然而，它依赖于一个很强的加性假设，我们认为，在实践中不成立，由于竞争的影响，我们建议通过明确优化这些影响，以提高数据驱动的方法。具体来说，我们投我们的问题作为最大化的近似submodular函数受拟阵约束，并证明了最坏情况下的保证经典的贪婪算法扩展到这个设置。然后，我们提出了三种不同的模型的竞争效果，并表明，他们都产生子模块化的目标。最后，我们通过模拟证明，我们的方法导致全面的显着收益。
Migration presents sweeping societal challenges that have recently attracted significant attention from the scientific community. One of the prominent approaches that have been suggested employs optimization and machine learning to match migrants to localities in a way that maximizes the expected number of migrants who find employment. However, it relies on a strong additivity assumption that, we argue, does not hold in practice, due to competition effects; we propose to enhance the data-driven approach by explicitly optimizing for these effects. Specifically, we cast our problem as the maximization of an approximately submodular function subject to matroid constraints, and prove that the worst-case guarantees given by the classic greedy algorithm extend to this setting. We then present three different models for competition effects, and show that they all give rise to submodular objectives. Finally, we demonstrate via simulations that our approach leads to significant gains across the board.