{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,11]],"date-time":"2026-11-11T07:41:16Z","timestamp":1794382876289,"version":"4.9.0"},"publisher-location":"Berlin, Heidelberg","reference-count":41,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642175718","type":"print"},{"value":"9783642175725","type":"electronic"}],"license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2010]]},"DOI":"10.1007\/978-3-642-17572-5_20","type":"book-chapter","created":{"date-parts":[[2010,12,6]],"date-time":"2010-12-06T03:54:45Z","timestamp":1291607685000},"page":"246-257","source":"Crossref","is-referenced-by-count":83,"title":["Constrained Non-monotone Submodular Maximization: Offline and Secretary Algorithms"],"prefix":"10.1007","author":[{"given":"Anupam","family":"Gupta","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aaron","family":"Roth","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Grant","family":"Schoenebeck","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kunal","family":"Talwar","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","reference":[{"key":"20_CR1","doi-asserted-by":"crossref","unstructured":"Agrawal, S., Ding, Y., Saberi, A., Ye, Y.: Correlation robust stochastic optimization. CoRR, abs\/0902.1792 (2009)","DOI":"10.1137\/1.9781611973075.88"},{"key":"20_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"477","DOI":"10.1007\/978-3-540-92185-1_53","volume-title":"Internet and Network Economics","author":"A. Asadpour","year":"2008","unstructured":"Asadpour, A., Nazerzadeh, H., Saberi, A.: Stochastic submodular maximization. In: Papadimitriou, C., Zhang, S. (eds.) WINE 2008. LNCS, vol.\u00a05385, pp. 477\u2013489. Springer, Heidelberg (2008)"},{"key":"20_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1007\/978-3-540-74208-1_2","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"M. Babaioff","year":"2007","unstructured":"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.\u00a04627, pp. 16\u201328. Springer, Heidelberg (2007)"},{"key":"20_CR4","doi-asserted-by":"crossref","unstructured":"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\u20131254 (2009)","DOI":"10.1137\/1.9781611973068.135"},{"key":"20_CR5","unstructured":"Babaioff, M., Immorlica, N., Kleinberg, R.: Matroids, secretary problems, and online mechanisms. In: SODA 2007, pp. 434\u2013443 (2007)"},{"key":"20_CR6","unstructured":"Bateni, M., Hajiaghayi, M., Zadimoghaddam, M.: Submodular secretary problem and extensions (2010) (manuscript), http:\/\/hdl.handle.net\/1721.1\/51336"},{"key":"20_CR7","doi-asserted-by":"crossref","unstructured":"Calinescu, G., Chekuri, C., P\u00e1l, M., Vondr\u00e1k, 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\u2013196 (2007)","DOI":"10.1007\/978-3-540-72792-7_15"},{"key":"20_CR8","unstructured":"Calinescu, G., Chekuri, C., P\u00e1l, M., Vondr\u00e1k, J.: Maximizing a monotone submodular function subject to a matroid constraint. To appear in SICOMP (2009)"},{"key":"20_CR9","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Khanna, S.: A polynomial time approximation scheme for the multiple knapsack problem. SIAM J. Comput. (electronic)\u00a035(3), 713\u2013728 (2005)","DOI":"10.1137\/S0097539700382820"},{"key":"#cr-split#-20_CR10.1","unstructured":"Chekuri, C., Vondr\u00e1k, J., Zenklusen, R.: Randomized pipage rounding for matroid polytopes and applications. CoRR, abs\/0909.4348 (2009);"},{"key":"#cr-split#-20_CR10.2","unstructured":"To appear in FOCS 2010"},{"key":"20_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"397","DOI":"10.1007\/978-3-540-70575-8_33","volume-title":"Automata, Languages and Programming","author":"N.B. Dimitrov","year":"2008","unstructured":"Dimitrov, N.B., Plaxton, C.G.: Competitive weighted matching in transversal matroids. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008, Part I. LNCS, vol.\u00a05125, pp. 397\u2013408. Springer, Heidelberg (2008)"},{"key":"20_CR12","first-page":"238","volume":"150","author":"E.B. Dynkin","year":"1963","unstructured":"Dynkin, E.B.: Optimal choice of the stopping moment of a Markov process. Dokl. Akad. Nauk SSSR\u00a0150, 238\u2013240 (1963)","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"20_CR13","doi-asserted-by":"crossref","unstructured":"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)","DOI":"10.1109\/FOCS.2007.29"},{"key":"20_CR14","doi-asserted-by":"publisher","first-page":"282","DOI":"10.1214\/ss\/1177012493","volume":"4","author":"T.S. Ferguson","year":"1989","unstructured":"Ferguson, T.S.: Who solved the secretary problem? Statistical Science\u00a04, 282\u2013296 (1989)","journal-title":"Statistical Science"},{"key":"#cr-split#-20_CR15.1","doi-asserted-by":"crossref","unstructured":"Fisher, M.L., Nemhauser, G.L., Wolsey, L.A.: An analysis of approximations for maximizing submodular set functions. II. Math. Programming Stud.\u00a0(8), 73\u201387 (1978);","DOI":"10.1007\/BFb0121195"},{"key":"#cr-split#-20_CR15.2","unstructured":"Polyhedral combinatorics"},{"issue":"2","key":"20_CR16","doi-asserted-by":"publisher","first-page":"189","DOI":"10.2307\/1402748","volume":"51","author":"P.R. Freeman","year":"1983","unstructured":"Freeman, P.R.: The secretary problem and its extensions: a review. Internat. Statist. Rev.\u00a051(2), 189\u2013206 (1983)","journal-title":"Internat. Statist. Rev."},{"key":"#cr-split#-20_CR17.1","unstructured":"Gupta, A., Nagarajan, V., Ravi, R.: Thresholded covering algorithms for robust and max-min optimization. CoRR, abs\/0912.1045 (2009);"},{"key":"#cr-split#-20_CR17.2","unstructured":"To appear in ICALP 2010"},{"key":"20_CR18","first-page":"71","volume-title":"EC 2004: Proceedings of the 5th ACM Conference on Electronic Commerce","author":"M.T. Hajiaghayi","year":"2004","unstructured":"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\u201380. ACM, New York (2004)"},{"key":"#cr-split#-20_CR19.1","doi-asserted-by":"crossref","unstructured":"Hausmann, D., Korte, B., Jenkyns, T.A.: Worst case analysis of greedy type algorithms for independence systems. Math. Programming Stud.\u00a0(12), 120\u2013131 (1980);","DOI":"10.1007\/BFb0120891"},{"key":"#cr-split#-20_CR19.2","unstructured":"Combinatorial optimization"},{"key":"20_CR20","unstructured":"Jenkyns, T.A.: The efficacy of the \u201cgreedy\u201d algorithm. In: Proceedings of the Seventh Southeastern Conference on Combinatorics, Graph Theory, and Computing (Louisiana State Univ., Baton Rouge, La., 1976), pp. 341\u2013350. Congressus Numerantium, No. XVII, Winnipeg, Man, Utilitas Math. (1976)"},{"key":"20_CR21","doi-asserted-by":"publisher","first-page":"137","DOI":"10.1145\/956750.956769","volume-title":"Proceedings of the Ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining","author":"D. Kempe","year":"2003","unstructured":"Kempe, D., Kleinberg, J., Tardos, \u00c9.: 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\u2013146. ACM, New York (2003)"},{"issue":"1","key":"20_CR22","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0020-0190(99)00031-9","volume":"70","author":"S. Khuller","year":"1999","unstructured":"Khuller, S., Moss, A., Naor, J.: The budgeted maximum coverage problem. Inform. Process. Lett.\u00a070(1), 39\u201345 (1999)","journal-title":"Inform. Process. Lett."},{"key":"20_CR23","first-page":"630","volume-title":"16th SODA","author":"R. Kleinberg","year":"2005","unstructured":"Kleinberg, R.: A multiple-choice secretary algorithm with applications to online auctions. In: 16th SODA, pp. 630\u2013631. ACM, New York (2005)"},{"key":"20_CR24","unstructured":"Kleinberg, R.D.: A secretary problem with submodular payoff function (2009) (manuscript)"},{"key":"#cr-split#-20_CR25.1","doi-asserted-by":"crossref","unstructured":"Korte, B., Hausmann, D.: An analysis of the greedy heuristic for independence systems. Ann. Discrete Math.\u00a02, 65\u201374 (1978);","DOI":"10.1016\/S0167-5060(08)70322-4"},{"key":"#cr-split#-20_CR25.2","unstructured":"Algorithmic aspects of combinatorics Conf., Vancouver Island, B.C. (1976)"},{"key":"20_CR26","doi-asserted-by":"crossref","unstructured":"Korula, N., P\u00e1l, M.: Algorithms for secretary problems on graphs and hypergraphs, pp. 508\u2013520 (2009)","DOI":"10.1007\/978-3-642-02930-1_42"},{"key":"20_CR27","doi-asserted-by":"crossref","unstructured":"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\u2013554 (2009)","DOI":"10.1137\/1.9781611973068.60"},{"key":"#cr-split#-20_CR28.1","doi-asserted-by":"crossref","unstructured":"Lee, J., Mirrokni, V.S., Nagarajan, V., Sviridenko, M.: Maximizing nonmonotone submodular functions under matroid or knapsack constraints. SIAM J. Discrete Math.\u00a023(4), 2053\u20132078 (2009\/2010);","DOI":"10.1137\/090750020"},{"key":"#cr-split#-20_CR28.2","unstructured":"Preliminary versions in STOC 2009 and arXiv:0902.0353"},{"key":"20_CR29","doi-asserted-by":"crossref","unstructured":"Lee, J., Sviridenko, M., Vondr\u00e1k, J.: Submodular maximization over multiple matroids via generalized exchange properties. In: Proceedings, International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp. 244\u2013257 (2009)","DOI":"10.1007\/978-3-642-03685-9_19"},{"key":"20_CR30","first-page":"134","volume-title":"Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing","author":"E. Mossel","year":"2007","unstructured":"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)"},{"issue":"3","key":"20_CR31","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"G.L. Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions. I. Math. Programming\u00a014(3), 265\u2013294 (1978)","journal-title":"I. Math. Programming"},{"issue":"1","key":"20_CR32","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0167-6377(03)00062-2","volume":"32","author":"M. Sviridenko","year":"2004","unstructured":"Sviridenko, M.: A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett.\u00a032(1), 41\u201343 (2004)","journal-title":"Oper. Res. Lett."},{"key":"20_CR33","doi-asserted-by":"crossref","unstructured":"Vondr\u00e1k, J.: Optimal approximation for the submodular welfare problem in the value oracle model. In: Proceedings, ACM Symposium on Theory of Computing, pp. 67\u201374 (2008)","DOI":"10.1145\/1374376.1374389"},{"key":"20_CR34","doi-asserted-by":"crossref","unstructured":"Vondr\u00e1k, J.: Symmetry and approximability of submodular maximization problems. In: Proceedings, IEEE Symposium on Foundations of Computer Science (2009) (page to appear)","DOI":"10.1109\/FOCS.2009.24"},{"issue":"3","key":"20_CR35","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1287\/moor.7.3.410","volume":"7","author":"L.A. Wolsey","year":"1982","unstructured":"Wolsey, L.A.: Maximising real-valued submodular functions: primal and dual heuristics for location problems. Math. Oper. Res.\u00a07(3), 410\u2013425 (1982)","journal-title":"Math. Oper. Res."}],"container-title":["Lecture Notes in Computer Science","Internet and Network Economics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-17572-5_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,6]],"date-time":"2019-06-06T16:54:37Z","timestamp":1559840077000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-17572-5_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010]]},"ISBN":["9783642175718","9783642175725"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-17572-5_20","relation":{"is-part-of":[{"id-type":"doi","id":"https:\/\/doi.org\/10.1007\/978-3-642-17572-5","asserted-by":"object"}]},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010]]}}}