A Unified Continuous Greedy Algorithm for Submodular Maximization
The paper discusses a unified continuous greedy algorithm for submodular maximization, exploring properties of set functions, submodular functions in combinatorics, polytope constraints, relaxation techniques, and the continuous greedy algorithm. It covers definitions, importance of submodularity, and practical applications in economics, game theory, and optimization.
Download Presentation

Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
A Unified Continuous Greedy Algorithm for Submodular Maximization Moran Feldman Joseph (Seffi) Naor Roy Schwartz Technion Israel Institute of Technology
Set Functions Definition Given a ground set E, a set function f : 2E assigns a number to every subset of the ground set. Properties Property Definition f( ) = 0 Normalization Monotonicity For every two sets A B E: f(A) f(B) Submodularity For all sets A, B E: f(A) + f(B) f(A B) + f(A B) 2
The Improtance of Submodularity Alternative (more intuitive) Definition A function f is submodular if for sets A B E and e B: f(A e) - f(A) f(B e) - f(B). The economy of scale feeling of this definition made submodular functions common in economics and game theory. Submodular Function in Combinatorics Submodular functions appear frequently in combinatorial settings. Here are two simple examples: Ground Set Submodular Function Nodes of a graph The number of edges leaving a set of nodes. Collection of sets The number of elements in the union of a sub-collection. 3
Polytope Constraints We abuse notation and identify a set S with its characteristic vector in [0, 1]E. Using this notation, we can define IP like problems: More generally, maximizing a submodular function subject to a polytope P constraint is the problem: ( ) x + max f . t . s 3 1 x 2 x 2 x 1 2 3 ( ) x max f + 3 3 x x x 1 2 3 E 1 , 0 E 1 , 0 . t . s x P x Difficulty: Generalizes integer programming . Unlikely to have a reasonable approximation. 4
Relaxation Replace the constraint x {0,1}E with x [0,1]E. Use the multilinear extension F (a.k.a. extension by expectation) [Calinescu et al. 07] as objective. Given a vector x, let R(x) denote a random set containing every element e E with probability xe independently. F(x)= E[f(R(x))]. The Problem Approximating the relaxed program. Motivation For many polytopes, a fractional solution can be rounded without losing too much in the objective. Matroid Polytopes no loss [Calinescu et al. 07]. Constant number of knapsacks (1 ) loss [Kulik et al. 09]. Unsplittable flow in trees O(1) loss [Chekuri et al. 11]. 5
The Continuous Greedy Algorithm The Algorithm [Vondrak 08] Let > 0 be a small number. 1. Initialize: y(0) and t 0. 2. While t < 1 do: 3. For every e E, let we = F(y(t) e) F(y(t)). 4. Find a solution x in P [0, 1]E maximizing w x. 5. y(t + ) y(t) + x 6. Set t t + 7. Return y(t) Remark If we cannot be evaluated directly, it can be approximated arbitrarily well via sampling. 6
The Continuous Greedy Algorithm - Demonstration 4 x 1 x 2 x y(0.04) 3 x y(0.03) y(0.02) y(0.01) y(0) Observations The algorithm is somewhat like gradient descending. The algorithm moves only in positive directions because the extension F is guaranteed to be concave in such directions. 7
The Continuous Greedy Algorithm - Analysis Theorem Assuming, f is a normalized monotone submodular function. P is a solvable polytope. The continuous greedy algorithm gives 1 1/e o(n-1) approximation. There are two important lemmata in the proof of the theorem. Lemma 1 There is a good direction, i.e., w x f(OPT) F(y(t)). Proof Idea OPT itself is a feasible direction, and its value is at least f(OPT) F(y(t)). 8
The Continuous Greedy Algorithm Analysis (cont.) Lemma 2 The improvement is related to w x, i.e., F(y(t + )) F(y(t)) + w x. Proof Since is small, F(y(t + )) - F(y(t)) e eF(y(t)) xe. We need to relate eF(y(t)) and we: F is multilinear, hence, we = F(y(t) e) F(y(t)) = (1 ye(t)) [F(y(t) e) F(y(t) - e)] = (1 ye(t)) eF(y(t)). F is monotone, hence eF(y(t)) is non-negative, and we eF(y(t)). ( ) ( ) e t y F ye ( ) t ( ) t ( ( ) t ) ( ( ) t ) e 1 ye F y F y 9
Insight Recall the equality we = (1 ye(t)) eF(y(t)). We used the monotonicity of f to get: we eF(y(t)). This is the most significant obstacle to extend the last algorithm to non-monotone functions. Idea: Currently the improvement in each step is proportional to: e eF(y(t)) xe We want it to be proportional to ewe xe = e (1 ye(t)) eF(y(t)) xe This can be done by increasing ye(t) only by xe (1 ye(t)), instead of by xe. 10
The Measured Continuous Greedy Algorithm The Algorithm Let > 0 be a small number. 1. Initialize: y(0) and t 0. 2. While t < T do: 3. For every e E, let we = F(y(t) e) F(y(t)). 4. Find a solution x in P [0, 1]E maximizing w x. 5. For every e E, ye(t + ) ye(t) + xe (1 ye(t)). 6. Set t t + 7. Return y(t) Remark The algorithm never leaves the box [0, 1]E, so it can be used with arbitrary values of T. 11
The Measured Continuous Greedy Algorithm - Analysis Theorem Assuming, f is a non-negative submodular function. P is a solvable down-montone polytope. The approximation ratio of the measured continuous greedy algorithm with T = 1is 1/e o(n-1). Remarks The solution is no longer a convex combination of P points. For T 1, the output is in P since P is down-monotone. 12
The Measured Continuous Greedy Algorithm Analysis (cont.) Lemma 2 The improvement is related to w x, i.e., F(y(t + )) F(y(t)) + w x. Proof The insight removes the only place in the previous proof of this lemma that used the monotonicity of f. Lemma 1 There is a good direction, i.e., w x e-t f(OPT) F(y(t)). Proof Idea Again, we show OPT itself is a good direction with at least that value. 13
Result for Monotone Functions For non-monotone functions, the approximation ratio is maximized for T = 1. For monotone f, we get the an approximation ratio of 1-e-T. For T = 1, this is the same ratio of the previous algorithm. The approximation ratio improves as T increases. In general, T > 1 might cause the algorithm to produce solutions outside the polytope. However, for some polytopes, somewhat larger values of T can be used. 14
The Submodular Welfare Problem Instance A set P of n players , and a set Q of m items. Normalized monotone submodular utility function wj: 2Q + for each player. Objective Let Qj Q denote the set of items the jth player gets. The utility of the jth player is wj(Qj). Distribute the items among the players, maximizing the sum of utilities. Approximation Can be represented as a problem of the previous form. The algorithm can be executed till time -n ln (1 1/n). The expected value of the solution is at least: 1 (1 1/n)n. 15
Open Problem The measured continuous greedy algorithm provides tight approximation for monotone functions [Vondrak 06]. Is this also the case for non-monotone functions? The current approximation ratio of e-1 is a natural number. 16