Roy Schwartz, Ph.D. Thesis Seminar
Wednesday, 4.4.2012, 12:30
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.