CAREER: New Algorithms for Submodular Optimization

职业：子模优化的新算法

基本信息

批准号：
1750333
负责人：
Alina Ene
金额：
$ 50.74万
依托单位：
Trustees of Boston University
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2018
资助国家：
美国
起止时间：
2018-02-01 至 2025-01-31
项目状态：
未结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1750333&HistoricalAwards=false
关键词：
CAREER New Algorithms Submodular Optimization

项目摘要

Submodular optimization provides general solutions to a wide range of applications from monitoring water distribution networks to summarizing large corpora of documents and speech recognition. Most of the existing submodular optimization algorithms are not suitable for modern datasets, since they are designed for worst-case instances and they suffer from prohibitive running times and poor empirical performance. This project aims to develop scalable algorithmic approaches with improved empirical performance for submodular optimization and to transfer theoretical insights to applications. The proposed research brings together insights from computer science, mathematics and optimization, and strengthens connections among these fields. The project will involve training the next wave of students and equipping them with technical tools to work in all these fields.The project focuses on three inter-related research directions in submodular function optimization: (a) Design faster algorithms for minimizing submodular functions with a decomposable or sum structure. The approach is to build on a rich set of tools from both discrete and continuous optimization. (b) Design algorithms for constrained submodular maximization problems with improved approximation guarantees and faster running times. The focus is on settling the approximability of constrained submodular maximization problems with a non-monotone objective and on designing faster algorithms for central families of constraints. (c) Design algorithms and frameworks for allocation or labeling problems with submodular costs. The main goal is to obtain more expressive algorithmic frameworks and efficient algorithms.

从监视水分配网络到总结大量文档和语音识别的大量应用程序，为广泛的应用提供了一般解决方案。大多数现有的下二次优化算法都不适合现代数据集，因为它们是为最坏情况而设计的，并且它们的运行时间和经验表现不佳。该项目旨在开发可扩展的算法方法，并改善了经验性能，以进行下义优化并将理论见解转移到应用程序中。拟议的研究汇集了计算机科学，数学和优化的见解，并加强了这些领域之间的联系。该项目将涉及培训下一波学生，并为他们提供在所有这些领域工作的技术工具。该项目重点介绍了三个相互关联的研究方向，以示例功能优化：（a）设计更快的算法，以最大程度地减少可分解或总和结构。该方法是基于离散和连续优化的一组丰富的工具。（b）设计算法，用于约束的近似值的近似值保证和更快的运行时间。重点是通过非单调目标解决受约束的下区性最大化问题的近似性，并针对约束中心家庭设计更快的算法。（c）设计算法和框架，用于分配或标记次数成本的问题。主要目标是获得更具表现力的算法框架和有效算法。