The Taub Faculty of Computer Science Events and Talks

The study of combinatorial problems with a submodular objective function has attracted much attention in recent years, and is partly motivated by the importance of such problems to combinatorial optimization, economics, and algorithmic game theory. A partial list of well-known problems captured by submodular maximization includes: Max-Cut, Max-DiCut, Max-k-Cover, Generalized-Assignment, several variants of Max-SAT and some welfare and scheduling problems.

While classical works on submodular maximization problems are mostly combinatorial in nature, many recent results are based on continuous algorithmic tools. Usually, the main bottleneck in such a continuous approach is how to approximately solve a non-convex relaxation for the submodular problem at hand. We present a new unified continuous greedy algorithm which finds approximate fractional solutions for both the non-monotone and monotone cases, and improves on the approximation ratio for various applications. Some notable immediate implications are information-theoretic tight approximations for Submodular Max-SAT and Submodular-Welfare with k players, for any number of players k, and an improved (1/e)-approximation for maximizing a non-monotone submodular function subject to a matroid or O(1)-knapsack constraints. We show that continuous methods can be further used to obtain improved results in other settings. Perhaps the most basic submodular maximization problem is the problem of Unconstrained Submodular Maximization, which captures some well-studied problems, such as: Max-Cut, Max-DiCut, and some variants of maximum facility location and Max-SAT. Exploiting some symmetry properties of the problem, we present a simple information-theoretic tight (1/2)-approximation algorithm, which unlike previous known algorithms keeps a fractional inner state, i.e., it is based on a continuous approach. We note that our algorithm can be further simplified to obtain a purely combinatorial algorithm which runs only in linear time.