AF: Small: Optimizing with Submodular Set Functions: Algorithms, Integrality Gaps and Structural Results

AF：小：使用子模集函数进行优化：算法、完整性差距和结构结果

• 批准号: 1526799
• 负责人: Chandra Chekuri
• 金额: $ 45万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-06-15 至 2020-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1526799&HistoricalAwards=false
• 关键词: AF; Small; Optimizing; Submodular; Set

Submodular set functions capture the notion of diminishing returns in an abstract and general way. For this reason they arise in numerous scenarios of interest and have been of much importance in classical combinatorial optimization. In the recent past there has been a substantial interest in optimization problems involving these functions due to a number of applications ranging from machine learning, algorithmic game theory, and information transmission in networks. The project focuses on a some canonical classes of optimization problems where submodularity plays a role in the objective function or constraints. The goal is to design fast and near-optimal algorithms for these canonical problems. Advances in the project will lead to improved algorithms, structural results, and insights into several application areas that were mentioned. The project will support and train two PhD students in the design and analysis of algorithms at the University of Illinois at Urbana-Champaign. The PI will complete a manuscript-length survey on submodular function maximization. The PI will develop and teach a course on recent advances on submodular functions at the University of Illinois. Lecture notes and related material will be made available to the public on the university's website.The technical focus of the project is to develop fast approximation algorithms for a number of fundamental problems involving submodular functions. The PI plans to build on the mathematical programming approach: relax the discrete optimization problem into a continuous optimization problem followed by appropriate rounding methods which would convert the fractional solution into an integer solution. The project will have four main thrusts.(i) Constrained Submodular Function Maximization: The goal is to obtain improved approximation algorithms for maximizing a given non-negative submodular function subject to a variety of independence (down-closed or packing) constraints. (ii) Constrained Submodular Function Minimization: The goal is to obtain improved approximation algorithms for minimizing a given non-negative submodular function subject to a variety of covering and allocation constraints.(iii) Faster algorithms: The goal is to obtain algorithms that are significantly faster than existing ones. The project will examine sequential algorithms as well as algorithms in the streaming and map-reduce models of computation.(iv) Submodularity in Information Transmission: The goal is to understand the capacity of networks for information transmission via flow-cut gaps in polymatroidal networks.

子管集功能以抽象和一般方式捕获回报减少的概念。因此，它们在许多感兴趣的情况下出现，并且在古典组合优化中非常重要。在最近的过去，由于许多应用程序，从机器学习，算法游戏理论和网络中的信息传输范围内，涉及这些功能的优化问题引起了重大兴趣。该项目着重于某些规范的优化问题，这些问题在目标函数或约束中起着作用。目的是为这些规范问题设计快速而近乎最佳的算法。该项目的进步将导致提高算法，结构性结果以及对所提到的几个应用领域的见解。该项目将在伊利诺伊大学Urbana-Champaign大学的算法设计和分析中支持和培训两名博士学位学生。 PI将完成一项关于最大化函数的手稿长度调查。 PI将在伊利诺伊大学开发和教授有关最新进展的课程。讲义纸条和相关材料将在大学的网站上向公众提供。该项目的技术重点是为许多涉及少量功能的基本问题开发快速近似算法。 PI计划以数学编程方法为基础：将离散优化问题放在连续优化问题中，然后是适当的舍入方法，该方法将分数解决方案转换为整数解决方案。该项目将具有四个主要推力。（i）受约束的下函数最大化：目标是获得改进的近似算法，以最大程度地提高给定的非阴性下义函数，但受到各种独立性（下降或包装）约束的约束。 （ii）受约束的下二个功能最小化：目标是获得改进的近似算法，以最大程度地减少给定的非负性下一个功能，但要受到各种覆盖和分配约束的约束。（iii）更快的算法：目标是获得显着的算法，这些算法是显着的。比现有的快。该项目将检查流的计算流和地图还原模型中的顺序算法以及算法。（iv）信息传输中的次数：目标是了解网络通过多摩托网络中流动漏洞进行信息传输的能力。