3 ms·
very good point. actually, 1-1/e is only for monotone submodular function. for a general submodular function, 1/2 approximation ratio is the best you can get.
by baojian 8y ago
very good point. actually, 1-1/e is only for monotone submodular function. for a general submodular function, 1/2 approximation ratio is the best you can get.