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

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

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.