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.

子模集合函数以抽象和一般的方式捕获收益递减的概念。由于这个原因，它们出现在许多有趣的场景中，并且在经典组合优化中非常重要。最近，由于机器学习、算法博弈论和网络中的信息传输等应用，人们对涉及这些函数的优化问题产生了浓厚的兴趣。该项目重点研究了一些典型的优化问题，其中子模块化在目标函数或约束中起作用。目标是为这些典型问题设计快速且接近最优的算法。该项目的进展将导致改进的算法、结构结果和对前面提到的几个应用领域的见解。该项目将支持和培训伊利诺伊大学厄巴纳-香槟分校的两名算法设计和分析博士生。PI将完成一份关于子模块功能最大化的手稿长度调查。PI将在伊利诺伊大学开发并教授一门关于次模块函数最新进展的课程。课堂讲稿和相关材料将在大学网站上向公众开放。该项目的技术重点是为涉及子模块函数的一些基本问题开发快速逼近算法。PI计划建立在数学规划方法的基础上：将离散优化问题放宽为连续优化问题，然后采用适当的舍入方法，将分数解转换为整数解。该项目将有四个主要重点。(i)约束子模函数最大化：目标是获得改进的近似算法，用于最大化给定的非负子模函数，该函数受各种独立（下闭或填充）约束。（ii）约束子模函数最小化：目标是获得改进的近似算法，用于最小化受各种覆盖和分配约束的给定非负子模函数。（iii）更快的算法：目标是获得比现有算法快得多的算法。该项目将研究顺序算法以及流计算模型和映射简化模型中的算法。信息传输的次模块性：目标是了解网络通过多线形网络的截流缺口进行信息传输的能力。