CAREER: New Algorithms for Submodular Optimization

子模块优化为从监测配水网络到总结大型文档语料库和语音识别的广泛应用提供了通用解决方案。大多数现有的子模块优化算法不适合现代数据集，因为它们是为最坏情况的实例而设计的，并且它们具有令人望而却步的运行时间和较差的经验性能。该项目旨在开发可扩展的算法方法，改善子模块优化的经验性能，并将理论见解转移到应用程序中。拟议的研究汇集了计算机科学，数学和优化的见解，并加强了这些领域之间的联系。该项目将培训下一批学生，并为他们提供在所有这些领域工作的技术工具。该项目集中在次模函数优化的三个相互关联的研究方向：（a）设计更快的算法，以最小化具有可分解或求和结构的次模函数。该方法是建立在一套丰富的工具，从离散和连续优化。(b)具有改进的近似保证和更快的运行时间的约束子模最大化问题的设计算法。重点是解决约束次模最大化问题的非单调目标的逼近性和设计更快的算法的中央家庭的约束。(c)设计子模块成本分配或标记问题的算法和框架。主要目标是获得更有表现力的算法框架和高效的算法。

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.