Submodularity and Curvature : The Optimal Algorithm (Combinatorial Optimization and Discrete Algorithms)
Jan Vondrák · Kyoto University Research Information Repository (Kyoto University) · 2010
Let (X;) be a matroid and let f : 2^{ X} \r i ght ar r ow \mat hcal { R} +\mat hr m{ b} \mat hr m{ e} a monotone submodular function.The curvature of f is the minimum c\in[0 , 1 ] such that for any S\subset X and j\in X\backslash S, f(S\cup\{j\})-f(S)\geq(1-c)f(\{j\}) .We consider the optimization problem \displaystyle \max\{f(S) : S\in \mathcal{I}\}.It is known that the greedy algorithm yields a 1/2-approximation for this problem [10], and \ d i s p l a y s t y l e \ f r a c { 1 } { 1 + c } -approximation when f has curvature c[3].For the uniform matroid, it was known that the greedy algorithm yields an improved \di spl ayst yl e \f r ac{ 1} { c} ( 1-e^{ -c} ) -approximation [3].In this paper, we analyze the continuous greedy algorithm [19] and prove that it gives a \di spl ayst yl e \f r ac{ 1} { c} ( 1-e^{ -c} ) -approximation for any matroid.Moreover, we show that this holds for a relaxed notion of curvature, curvature with respect to the optimum, and we prove that any better approximation under these conditions would require an exponential number of value queries.§1.Introduction In this paper, we consider the following optimization problem: \displaystyle \max\{f(S):S\in \mathcal{I}\} where f : 2{X} \r i ght ar r ow \mat hcal { R} +\mat hr m{ i } \mat hr m{ s } a monotone submodular function, and \mathcal {I}\subset 2^{X} is the collection of independent sets in a matroid.A function f is monotone if f(A)\leq f(A') for any A\subset A' , and f is submodular if f(A\cup B)+f(A\cap B)\leq f(A)+f(B) for all A, B .For the definition of a matroid, see Section 2. For computational purposes, we will assume that f and \ma t hc a l { I } are specified by value/membership oracles, which can be queried polynomially many times.We call this framework the value oracle model.