Social networks and discovery in the enterprise (SaND)
Inbal Ronen, Elad Shahar, et al.
SIGIR 2009
Let f: 2 X → R + be a monotone submodular set function, and let (X, I) be a matroid. We consider the problem max s∈If(S). It is known that the greedy algorithm yields a 1/2-approximation [M. L. Fisher, G. L. Nemhauser, and L. A. Wolsey, Math. Programming Stud., no. 8(1978), pp. 73-87] for this problem. For certain special cases, e.g., max |S|≤kf (S), the greedy algorithm yields a (1-1/e)-approximation. It is known that this is optimal both in the value oracle model (where the only access to f is through a black box returning f(S) for a given set S) [G. L. Nemhauser and L. A. Wolsey, Math. Oper. Res., 3(1978), pp. 177-188] and for explicitly posed instances assuming P = NP [U. Feige, J. ACM, 45(1998), pp. 634-652]. In this paper, we provide a randomized (1-1/e)-approximation for any monotone submodular function and an arbitrary matroid. The algorithm works in the value oracle model. Our main tools are a variant of the pipage rounding technique of Ageev and Sviridenko [J. Combin. Optim., 8(2004), pp. 307-328], and a continuous greedy process that may be of independent interest. As a special case, our algorithm implies an optimal approximation for the submodular welfare problem in the value oracle model [J. Vondrák, Proceedings of the 38th ACM Symposium on Theory of Computing, 2008, pp. 67-74]. As a second application, we show that the generalized assignment problem (GAP) is also a special case; although the reduction requires |X| to be exponential in the original problem size, we are able to achieve a (1-1/e - o(1))-approximation for GAP, simplifying previously known algorithms. Additionally, the reduction enables us to obtain approximation algorithms for variants of GAP with more general constraints. © 2011 Society for Industrial and Applied Mathematics.
Inbal Ronen, Elad Shahar, et al.
SIGIR 2009
Maciel Zortea, Miguel Paredes, et al.
IGARSS 2021
S.M. Sadjadi, S. Chen, et al.
TAPIA 2009
Raghu Krishnapuram, Krishna Kummamuru
IFSA 2003