×

Constrained submodular maximization via greedy local search. (English) Zbl 1476.90289

Summary: We present a simple combinatorial \(\frac{1 - e^{- 2}}{2} \)-approximation algorithm for maximizing a monotone submodular function subject to a knapsack and a matroid constraint. This classic problem is known to be hard to approximate within factor better than \(1 - 1/e\). We extend the algorithm to yield \(\frac{1 - e^{-(k + 1)}}{k + 1}\) approximation for submodular maximization subject to a single knapsack and \(k\) matroid constraints, for any fixed \(k > 1\). Our algorithms, which combine the greedy algorithm of S. Khuller et al. [Inf. Process. Lett. 70, No. 1, 39–45 (1999; Zbl 1002.68203)] and M. Sviridenko [Oper. Res. Lett. 32, No. 1, 41–43 (2004; Zbl 1056.90124)] with local search, show the power of this natural framework in submodular maximization with combined constraints.

MSC:

90C27 Combinatorial optimization
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Badanidiyuru, A.; Vondrák, J., Fast algorithms for maximizing submodular functions, (Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (2014)), 1497-1514 · Zbl 1422.68286
[2] Calinescu, G.; Chekuri, C.; Pál, M.; Vondrák, J., Maximizing a monotone submodular function subject to a matroid constraint, SIAM J. Comput., 40, 6, 1740-1766 (2011) · Zbl 1234.68459
[3] Chekuri, C.; Vondrák, J.; Zenklusen, R., Dependent randomized rounding via exchange properties of combinatorial structures, (Proceedings of the 51st Annual IEEE Symposium on Foundations of Computer Science (2010)), 575-584
[4] Chekuri, C.; Vondrák, J.; Zenklusen, R., Submodular function maximization via the multilinear relaxation and contention resolution schemes, SIAM J. Comput., 43, 6, 1831-1879 (2014) · Zbl 1437.90135
[5] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C., Introduction to Algorithms (2001), MIT press: MIT press Cambridge · Zbl 1047.68161
[6] Feige, U., A threshold of \(\ln n\) for approximating set cover, J. ACM, 45, 4, 634-652 (1998) · Zbl 1065.68573
[7] Feldman, M., Maximization Problems with Submodular Objective Functions (2013), Computer Science Department: Computer Science Department Technion, (Ph.D. thesis)
[8] Feldman, M.; Naor, J.; Schwartz, R., A unified continuous greedy algorithm for submodular maximization, (Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (2011)), 570-579 · Zbl 1292.90248
[9] Filmus, Y.; Ward, J., A tight combinatorial algorithm for submodular maximization subject to a matroid constraint, (Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (2012)), 659-668
[10] Fisher, M.; Nemhauser, G.; Wolsey, L., An analysis of approximations for maximizing submodular set functions—ii, Polyhedral Combin., 73-87 (1978) · Zbl 0408.90085
[11] Gupta, A.; Nagarajan, V.; Ravi, R., Robust and maxmin optimization under matroid and knapsack uncertainty sets, ACM Trans. Algorithms, 12, 1, 10 (2016) · Zbl 1398.68689
[12] Hazan, E.; Safra, S.; Schwartz, O., On the complexity of approximating k-set packing, Comput. Complexity, 15, 1, 20-39 (2006) · Zbl 1103.90105
[13] Khuller, S.; Moss, A.; Naor, J., The budgeted maximum coverage problem, Inf. Process. Lett., 70, 1, 39-45 (1999) · Zbl 1002.68203
[14] Krause, A.; Leskovec, J.; Guestrin, C.; VanBriesen, J.; Faloutsos, C., Efficient sensor placement optimization for securing large water distribution networks, J. Water Resour. Plann. Manag., 134, 6, 516-526 (2008)
[15] Lee, J.; Mirrokni, V. S.; Nagarajan, V.; Sviridenko, M., Maximizing nonmonotone submodular functions under matroid or knapsack constraints, SIAM J. Discrete Math., 23, 4, 2053-2078 (2010) · Zbl 1207.68445
[16] Nemhauser, G.; Wolsey, L., Best algorithms for approximating the maximum of submodular set function, Math. Oper. Res., 3, 3, 177-188 (1978) · Zbl 0395.90072
[17] Nemhauser, G.; Wolsey, L.; Fisher, M., An analysis of the approximations for maximizing submodular set functions - i, Math. Program., 14, 265-294 (1978) · Zbl 0374.90045
[18] K.K. Sarpatwar, B. Schieber, H. Shachnai, Constrained submodular maximization via greedy local search, CoRR abs/1705.06319.; K.K. Sarpatwar, B. Schieber, H. Shachnai, Constrained submodular maximization via greedy local search, CoRR abs/1705.06319.
[19] Sviridenko, M., A note on maximizing a submodular set function subject to knapsack constraint, Oper. Res. Lett., 32, 41-43 (2004) · Zbl 1056.90124
[20] Vondrák, J., Optimal approximation for the submodular welfare problem in the value oracle model, (Proceedings of the 40th annual ACM symposium on Theory of computing (2008)), 67-74 · Zbl 1231.91094
[21] Wolsey, L. A., Maximizing real-valued submodular functions: Primal and dual heuristics for location problems, Math. Oper. Res., 7, 410-425 (1982) · Zbl 0498.90024
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.