Practical Algorithms for Applied Submodular Optimization

应用子模优化的实用算法

• 批准号: 1160915
• 负责人: Jonathan Lee
• 金额: $ 26万
• 依托单位: Regents of the University of Michigan - Ann Arbor
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-05-01 至 2016-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1160915&HistoricalAwards=false
• 关键词: Practical; Algorithms; 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.

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