Abstract
Constrained submodular maximization problems have long been studied, most recently in the context of auctions and computational advertising, with near-optimal results known under a variety of constraints when the submodular function is monotone. In this paper, we give constant approximation algorithms for the non-monotone case that work for p-independence systems (which generalize constraints given by the intersection of p matroids that had been studied previously), where the running time is \(\text{poly}(n,p)\). Our algorithms and analyses are simple, and essentially reduce non-monotone maximization to multiple runs of the greedy algorithm previously used in the monotone case.
We extend these ideas to give a simple greedy-based constant factor algorithms for non-monotone submodular maximization subject to a knapsack constraint, and for (online) secretary setting (where elements arrive one at a time in random order and the algorithm must make irrevocable decisions) subject to uniform matroid or a partition matroid constraint. Finally, we give an O(logk) approximation in the secretary setting subject to a general matroid constraint of rank k.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Agrawal, S., Ding, Y., Saberi, A., Ye, Y.: Correlation robust stochastic optimization. CoRR, abs/0902.1792 (2009)
Asadpour, A., Nazerzadeh, H., Saberi, A.: Stochastic submodular maximization. In: Papadimitriou, C., Zhang, S. (eds.) WINE 2008. LNCS, vol. 5385, pp. 477–489. Springer, Heidelberg (2008)
Babaioff, M., Immorlica, N., Kempe, D., Kleinberg, R.: A knapsack secretary problem with applications. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) RANDOM 2007 and APPROX 2007. LNCS, vol. 4627, pp. 16–28. Springer, Heidelberg (2007)
Babaioff, M., Dinitz, M., Gupta, A., Immorlica, N., Talwar, K.: Secretary problems: weights and discounts. In: 19th Proceedings of ACM-SIAM Symposium on Discrete Algorithms, pp. 1245–1254 (2009)
Babaioff, M., Immorlica, N., Kleinberg, R.: Matroids, secretary problems, and online mechanisms. In: SODA 2007, pp. 434–443 (2007)
Bateni, M., Hajiaghayi, M., Zadimoghaddam, M.: Submodular secretary problem and extensions (2010) (manuscript), http://hdl.handle.net/1721.1/51336
Calinescu, G., Chekuri, C., Pál, M., Vondrák, J.: Maximizing a submodular set function subject to a matroid constraint (extended abstract). In: Proceedings, MPS Conference on Integer Programming and Combinatorial Optimization, pp. 182–196 (2007)
Calinescu, G., Chekuri, C., Pál, M., Vondrák, J.: Maximizing a monotone submodular function subject to a matroid constraint. To appear in SICOMP (2009)
Chekuri, C., Khanna, S.: A polynomial time approximation scheme for the multiple knapsack problem. SIAM J. Comput. (electronic) 35(3), 713–728 (2005)
Chekuri, C., Vondrák, J., Zenklusen, R.: Randomized pipage rounding for matroid polytopes and applications. CoRR, abs/0909.4348 (2009); To appear in FOCS 2010
Dimitrov, N.B., Plaxton, C.G.: Competitive weighted matching in transversal matroids. In: Aceto, L., Damgård, I., Goldberg, L.A., Halldórsson, M.M., Ingólfsdóttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol. 5125, pp. 397–408. Springer, Heidelberg (2008)
Dynkin, E.B.: Optimal choice of the stopping moment of a Markov process. Dokl. Akad. Nauk SSSR 150, 238–240 (1963)
Feige, U., Mirrokni, V., Vondrak, J.: Maximizing non-monotone submodular functions. In: Proceedings of 48th Annual IEEE Symposium on Foundations of Computer Science, FOCS (2007)
Ferguson, T.S.: Who solved the secretary problem? Statistical Science 4, 282–296 (1989)
Fisher, M.L., Nemhauser, G.L., Wolsey, L.A.: An analysis of approximations for maximizing submodular set functions. II. Math. Programming Stud. (8), 73–87 (1978); Polyhedral combinatorics
Freeman, P.R.: The secretary problem and its extensions: a review. Internat. Statist. Rev. 51(2), 189–206 (1983)
Gupta, A., Nagarajan, V., Ravi, R.: Thresholded covering algorithms for robust and max-min optimization. CoRR, abs/0912.1045 (2009); To appear in ICALP 2010
Hajiaghayi, M.T., Kleinberg, R., Parkes, D.C.: Adaptive limited-supply online auctions. In: EC 2004: Proceedings of the 5th ACM Conference on Electronic Commerce, pp. 71–80. ACM, New York (2004)
Hausmann, D., Korte, B., Jenkyns, T.A.: Worst case analysis of greedy type algorithms for independence systems. Math. Programming Stud. (12), 120–131 (1980); Combinatorial optimization
Jenkyns, T.A.: The efficacy of the “greedy” algorithm. In: Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing (Louisiana State Univ., Baton Rouge, La., 1976), pp. 341–350. Congressus Numerantium, No. XVII, Winnipeg, Man, Utilitas Math. (1976)
Kempe, D., Kleinberg, J., Tardos, É.: Maximizing the spread of influence through a social network. In: Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 137–146. ACM, New York (2003)
Khuller, S., Moss, A., Naor, J.: The budgeted maximum coverage problem. Inform. Process. Lett. 70(1), 39–45 (1999)
Kleinberg, R.: A multiple-choice secretary algorithm with applications to online auctions. In: 16th SODA, pp. 630–631. ACM, New York (2005)
Kleinberg, R.D.: A secretary problem with submodular payoff function (2009) (manuscript)
Korte, B., Hausmann, D.: An analysis of the greedy heuristic for independence systems. Ann. Discrete Math. 2, 65–74 (1978); Algorithmic aspects of combinatorics Conf., Vancouver Island, B.C. (1976)
Korula, N., Pál, M.: Algorithms for secretary problems on graphs and hypergraphs, pp. 508–520 (2009)
Kulik, A., Shachnai, H., Tamir, T.: Maximizing submodular set functions subject to multiple linear constraints. In: SODA 2009: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 545–554 (2009)
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 (2009/2010); Preliminary versions in STOC 2009 and arXiv:0902.0353
Lee, J., Sviridenko, M., Vondrák, J.: Submodular maximization over multiple matroids via generalized exchange properties. In: Proceedings, International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp. 244–257 (2009)
Mossel, E., Roch, S.: On the submodularity of influence in social networks. In: Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing, p. 134. ACM, New York (2007)
Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions. I. Math. Programming 14(3), 265–294 (1978)
Sviridenko, M.: A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett. 32(1), 41–43 (2004)
Vondrák, J.: Optimal approximation for the submodular welfare problem in the value oracle model. In: Proceedings, ACM Symposium on Theory of Computing, pp. 67–74 (2008)
Vondrák, J.: Symmetry and approximability of submodular maximization problems. In: Proceedings, IEEE Symposium on Foundations of Computer Science (2009) (page to appear)
Wolsey, L.A.: Maximising real-valued submodular functions: primal and dual heuristics for location problems. Math. Oper. Res. 7(3), 410–425 (1982)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Gupta, A., Roth, A., Schoenebeck, G., Talwar, K. (2010). Constrained Non-monotone Submodular Maximization: Offline and Secretary Algorithms. In: Saberi, A. (eds) Internet and Network Economics. WINE 2010. Lecture Notes in Computer Science, vol 6484. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-17572-5_20
Download citation
DOI: https://doi.org/10.1007/978-3-642-17572-5_20
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-17571-8
Online ISBN: 978-3-642-17572-5
eBook Packages: Computer ScienceComputer Science (R0)