{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:36:44Z","timestamp":1759639004082},"publisher-location":"Berlin, Heidelberg","reference-count":25,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783642229343"},{"type":"electronic","value":"9783642229350"}],"license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"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":[[2011]]},"DOI":"10.1007\/978-3-642-22935-0_19","type":"book-chapter","created":{"date-parts":[[2011,8,12]],"date-time":"2011-08-12T09:20:39Z","timestamp":1313140839000},"page":"218-229","source":"Crossref","is-referenced-by-count":17,"title":["Improved Competitive Ratios for Submodular Secretary Problems (Extended Abstract)"],"prefix":"10.1007","author":[{"given":"Moran","family":"Feldman","sequence":"first","affiliation":[]},{"given":"Joseph","family":"Naor","sequence":"additional","affiliation":[]},{"given":"Roy","family":"Schwartz","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"issue":"1","key":"19_CR1","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0895480195290017","volume":"14","author":"M. Ajtai","year":"2001","unstructured":"Ajtai, M., Megiddo, N., Waarts, O.: Improved algorithms and analysis for secretary problems and generalizations. SIAM J. Discrete Math.\u00a014(1), 1\u201327 (2001)","journal-title":"SIAM J. Discrete Math."},{"key":"19_CR2","doi-asserted-by":"publisher","first-page":"1245","DOI":"10.1137\/1.9781611973068.135","volume-title":"20th ACM-SIAM Symposium on Discrete Algorithms","author":"M. Babaioff","year":"2009","unstructured":"Babaioff, M., Dinitz, M., Gupta, A., Immorlica, N., Talwar, K.: Secretary problems: Weights and discounts. In: 20th ACM-SIAM Symposium on Discrete Algorithms, pp. 1245\u20131254. Society for Industrial and Applied Mathematics, Philadelphia (2009)"},{"key":"19_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":"19_CR4","first-page":"434","volume-title":"18th ACM-SIAM Symposium on Discrete Algorithms","author":"M. Babaioff","year":"2007","unstructured":"Babaioff, M., Immorlica, N., Kleinberg, R.: Matroids, secretary problems, and online mechanisms. In: 18th ACM-SIAM Symposium on Discrete Algorithms, pp. 434\u2013443. Society for Industrial and Applied Mathematics, Philadelphia (2007)"},{"key":"19_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1007\/978-3-642-15369-3_4","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"M.H. Bateni","year":"2010","unstructured":"Bateni, M.H., Hajiaghayi, M.T., Zadimoghaddam, M.: Submodular secretary problem and extensions. In: Serna, M., Shaltiel, R., Jansen, K., Rolim, J. (eds.) APPROX 2010, LNCS, vol.\u00a06302, pp. 39\u201352. Springer, Heidelberg (2010)"},{"key":"19_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"163","DOI":"10.1007\/978-3-642-13036-6_13","volume-title":"Integer Programming and Combinatorial Optimization","author":"N. Buchbinder","year":"2010","unstructured":"Buchbinder, N., Jain, K., Singh, M.: Secretary problems via linear programming. In: Eisenbrand, F., Shepherd, F.B. (eds.) IPCO 2010. LNCS, vol.\u00a06080, pp. 163\u2013176. Springer, Heidelberg (2010)"},{"key":"19_CR7","unstructured":"Calinescu, G., Chekuri, C., P\u00e1l, M., Vondr\u00e1k, J.: Maximizing a monotone submodular function subject to a matroid constraint. To appear in SIAM J. Comput."},{"key":"19_CR8","first-page":"783","volume-title":"42nd ACM Symposium on Theory of Computer Science","author":"C. Chekuri","year":"2011","unstructured":"Chekuri, C., Vondr\u00e1k, J., Zenklusen, R.: Submodular function maximization via the multilinear relaxation and contention resolution schemes. In: 42nd ACM Symposium on Theory of Computer Science, pp. 783\u2013792. ACM, New York (2011)"},{"key":"19_CR9","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":"19_CR10","first-page":"627","volume":"4","author":"E.B. Dynkin","year":"1963","unstructured":"Dynkin, E.B.: The optimum choice of the instant for stopping a markov process. Sov. Math. Dokl.\u00a04, 627\u2013629 (1963)","journal-title":"Sov. Math. Dokl."},{"issue":"1","key":"19_CR11","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1137\/070680977","volume":"39","author":"U. Feige","year":"2009","unstructured":"Feige, U.: On maximizing welfare when utility functions are subadditive. SIAM J. Comput.\u00a039(1), 122\u2013142 (2009)","journal-title":"SIAM J. Comput."},{"key":"19_CR12","first-page":"461","volume-title":"48th Annual IEEE Symposium on Foundations of Computer Science","author":"U. Feige","year":"2007","unstructured":"Feige, U., Mirrokni, V.S., Vondr\u00e1k, J.: Maximizing non-monotone submodular functions. In: 48th Annual IEEE Symposium on Foundations of Computer Science, pp. 461\u2013471. IEEE Computer Society, Washington DC (2007)"},{"issue":"3","key":"19_CR13","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(3), 282\u2013289 (1989)","journal-title":"Statistical Science"},{"issue":"2","key":"19_CR14","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. International Statistical Review\u00a051(2), 189\u2013206 (1983)","journal-title":"International Statistical Review"},{"key":"19_CR15","doi-asserted-by":"crossref","unstructured":"Gharan, S.O., Vondr\u00e1k, J.: Submodular maximization by simulated annealing. In: 22nd ACM-SIAM Symposium on Discrete Algorithms, pp. 1096\u20131116 (2011)","DOI":"10.1137\/1.9781611973082.83"},{"key":"19_CR16","series-title":"Springer Series in Statistics","doi-asserted-by":"publisher","first-page":"355","DOI":"10.1007\/978-0-387-44956-2_22","volume-title":"Selected Papers of Frederick Mosteller","author":"J. Gilbert","year":"2006","unstructured":"Gilbert, J., Mosteller, F.: Recognizing the maximum of a sequence. In: Fienberg, S., Hoaglin, D. (eds.) Selected Papers of Frederick Mosteller. Springer Series in Statistics, pp. 355\u2013398. Springer, New York (2006)"},{"key":"19_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"246","DOI":"10.1007\/978-3-642-17572-5_20","volume-title":"Internet and Network Economics","author":"A. Gupta","year":"2010","unstructured":"Gupta, A., Roth, A., Schoenebeck, G., Talwar, K.: Constrained non-monotone submodular maximization: Offline and secretary algorithms. In: Saberi, A. (ed.) WINE 2010. LNCS, vol.\u00a06484, pp. 246\u2013257. Springer, Heidelberg (2010)"},{"key":"19_CR18","doi-asserted-by":"crossref","unstructured":"Im, S., Wang, Y.: Secretary problems: Laminar matroid and interval scheduling. In: 22nd ACM-SIAM Symposium on Discrete Algorithms, pp. 1096\u20131116 (2011)","DOI":"10.1137\/1.9781611973082.96"},{"key":"19_CR19","first-page":"630","volume-title":"16th ACM-SIAM Symposium on Discrete Algorithms","author":"R.. Kleinberg","year":"2005","unstructured":"Kleinberg, R.: A multiple-choice secretary algorithm with applications to online auctions. In: 16th ACM-SIAM Symposium on Discrete Algorithms, pp. 630\u2013631. Society for Industrial and Applied Mathematics, Philadelphia (2005)"},{"key":"19_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"508","DOI":"10.1007\/978-3-642-02930-1_42","volume-title":"Automata, Languages and Programming","author":"N. Korula","year":"2009","unstructured":"Korula, N., P\u00e1l, M.: Algorithms for secretary problems on graphs and hypergraphs. In: Albers, S., Marchetti-Spaccamela, A., Matias, Y., Nikoletseas, S., Thomas, W. (eds.) ICALP 2009. LNCS, vol.\u00a05556, pp. 508\u2013520. Springer, Heidelberg (2009)"},{"key":"19_CR21","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1137\/1.9781611973068.60","volume-title":"20th ACM-SIAM Symposium on Discrete Algorithms","author":"A. Kulik","year":"2009","unstructured":"Kulik, A., Shachnai, H., Tamir, T.: Maximizing submodular set functions subject to multiple linear constraints. In: 20th ACM-SIAM Symposium on Discrete Algorithms, pp. 545\u2013554. Society for Industrial and Applied Mathematics, Philadelphia (2009)"},{"issue":"4","key":"19_CR22","doi-asserted-by":"publisher","first-page":"2053","DOI":"10.1137\/090750020","volume":"23","author":"J. Lee","year":"2010","unstructured":"Lee, J., Mirrokni, V.S., Nagarajan, V., Sviridenko, M.: Maximizing non-monotone submodular functions under matroid or knapsack constraints. SIAM J. Discrete Mathematics\u00a023(4), 2053\u20132078 (2010)","journal-title":"SIAM J. Discrete Mathematics"},{"key":"19_CR23","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/978-3-642-03685-9_19","volume-title":"12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems","author":"J. Lee","year":"2009","unstructured":"Lee, J., Sviridenko, M., Vondr\u00e1k, J.: Submodular maximization over multiple matroids via generalized exchange properties. In: 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, pp. 244\u2013257. Springer, Heidelberg (2009)"},{"key":"19_CR24","doi-asserted-by":"publisher","first-page":"39","DOI":"10.2307\/2985407","volume":"10","author":"D.V. Lindley","year":"1961","unstructured":"Lindley, D.V.: Dynamic programming and decision theory. Applied Statistics\u00a010, 39\u201351 (1961)","journal-title":"Applied Statistics"},{"key":"19_CR25","first-page":"651","volume-title":"50th Annual IEEE Symposium on Foundations of Computer Science","author":"J. Vondr\u00e1k","year":"2009","unstructured":"Vondr\u00e1k, J.: Symmetry and approximability of submodular maximization problems. In: 50th Annual IEEE Symposium on Foundations of Computer Science, pp. 651\u2013670. IEEE Computer Society, Washington DC (2009)"}],"container-title":["Lecture Notes in Computer Science","Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-22935-0_19","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,31]],"date-time":"2019-03-31T12:04:09Z","timestamp":1554033849000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-22935-0_19"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011]]},"ISBN":["9783642229343","9783642229350"],"references-count":25,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-22935-0_19","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2011]]}}}