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

University Of Illinois At Urbana-Champaign, Urbana IL

Investigators

Abstract

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.