Practical Algorithms for Applied Submodular Optimization

该奖项通过推广和扩展在特定应用领域取得成功的数学优化和近似方法，为一般子模块优化问题的实际精确和近似算法的开发和分析提供资金。重要的应用领域包括环境监测网络的重新设计和布尔二次优化。到目前为止，一般的子模块优化技术都是为了提供可证明的良好的最坏情况行为而开发的。另一方面，一些实用的算法，不受理论要求的阻碍，已经开发并实现了一些特殊情况。本项目旨在将这种成功推广到一般情况。算法将作为开源软件实例化和分发，从而提供实用的、通用的工具来解决这个无处不在的问题类。通过黑盒（即，函数评估子程序）定义特定的特殊情况，此类软件将在各种应用领域具有广泛的适用性，例如经济学，机器学习，生物多样性保护和静力学。此外，该项目属于更广泛的非线性离散优化领域，自然期望在这一重要的当前主题中产生更广泛的影响。

This award provides funding for the development and analysis of practical exact and approximation algorithms for general submodular optimization problems, by generalizing and extending mathematical-optimization and approximation methods that have been successful in specific application areas. Important application areas include redesigning environmental monitoring networks and Boolean quadratic optimization. Thus far, general techniques for submodular optimization have been developed with the aim of providing provably good worst-case behavior. On the other hand, practical algorithms, not encumbered by theoretical requirements, have been developed and implemented for several special cases. This project is aimed at extending such success to the general case.Algorithms will be instantiated and distributed as open-source software thus providing practical, general-purpose tools for attacking this ubiquitous problem class. With particular special cases defined through a black box (i.e., a function-evaluation subroutine), such software will have broad applicability across a variety of application areas, such as economics, machine learning, biodiversity conservation and statics. Moreover, the project is within the broader area of nonlinear discrete optimization, and it is natural to expect to have a broader influence within this important current topic.