Computer Science Colloquia: Sun, Dec 11 at 11:00 - Roy Schwartz
Niv Buchbinder
Dear all,
Next week we are happy to have Roy Schwartz from the Faculty of Computer Science, Technion.
You can view the upcoming talks of the seminar at:
See you,
Niv Buchbinder.
%%%%%%%%%%%%%%%%%%%%%%
Computer Science Colloquia - Open University of Israel
%%%%%%%%%%%%%%%%%%%%%%
Time: Sunday, December 11, at 11:00-12:00
Place: Visitor center 194, Open University.
Speaker: Roy Schwartz, Faculty of Computer Science, Technion.
-------
Title: A Unified Continuous Greedy Algorithm for Submodular Maximization
-------
Abstract:
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 economics, algorithmic game theory and combinatorial optimization. Classical works on these problems are mostly combinatorial in nature. Recently, however, many results based on continuous algorithmic tools have emerged. The main bottleneck of such continuous techniques is how to approximately solve a non-convex relaxation for the submodular problem at hand. Thus, the efficient computation of better fractional solutions immediately implies improved approximations for numerous applications. A simple and elegant method, called ``continuous greedy'', successfully tackles this issue for monotone submodular objective functions, however, only much more complex tools are known to work for general non-monotone submodular objectives.
In this work 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 many applications. For general non-monotone submodular objective functions, our algorithm achieves an improved approximation ratio of $1/e$. For monotone submodular objective functions, our algorithm achieves an approximation ratio that depends on the density of the polytope defined by the problem at hand, which is always at least as good as the previously known best approximation ratio of $1 - 1/e$. Some notable immediate implications are an improved $1/e$-approximation for maximizing a non-monotone submodular function subject to a matroid or $O(1)$-knapsack constraints, and information-theoretic tight approximations for Submodular-Max-SAT and Submodular-Welfare with $k$ players, for {\em any} number of players $k$.