{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,9]],"date-time":"2024-09-09T13:24:27Z","timestamp":1725888267433},"publisher-location":"Cham","reference-count":27,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319592497"},{"type":"electronic","value":"9783319592503"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"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":[[2017]]},"DOI":"10.1007\/978-3-319-59250-3_26","type":"book-chapter","created":{"date-parts":[[2017,5,23]],"date-time":"2017-05-23T09:04:39Z","timestamp":1495530279000},"page":"317-329","source":"Crossref","is-referenced-by-count":2,"title":["Adaptive Submodular Ranking"],"prefix":"10.1007","author":[{"given":"Prabhanjan","family":"Kambadur","sequence":"first","affiliation":[]},{"given":"Viswanath","family":"Nagarajan","sequence":"additional","affiliation":[]},{"given":"Fatemeh","family":"Navidi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,5,24]]},"reference":[{"issue":"3\u20134","key":"26_CR1","doi-asserted-by":"crossref","first-page":"1112","DOI":"10.1007\/s00453-011-9510-9","volume":"62","author":"M Adler","year":"2012","unstructured":"Adler, M., Heeringa, B.: Approximating optimal binary decision trees. Algorithmica 62(3\u20134), 1112\u20131121 (2012)","journal-title":"Algorithmica"},{"key":"26_CR2","doi-asserted-by":"crossref","unstructured":"Azar, Y., Gamzu, I.: Ranking with submodular valuations. In: SODA, pp. 1070\u20131079 (2011)","DOI":"10.1137\/1.9781611973082.81"},{"key":"26_CR3","doi-asserted-by":"crossref","unstructured":"Azar, Y., Gamzu, I., Yin, X.: Multiple intents re-ranking. In: STOC, pp. 669\u2013678 (2009)","DOI":"10.1145\/1536414.1536505"},{"key":"26_CR4","doi-asserted-by":"crossref","unstructured":"Bansal, N., Gupta, A., Krishnaswamy, R.: A constant factor approximation algorithm for generalized min-sum set cover. In: SODA, pp. 1539\u20131545 (2010)","DOI":"10.1137\/1.9781611973075.125"},{"issue":"4","key":"26_CR5","doi-asserted-by":"crossref","first-page":"733","DOI":"10.1007\/s00453-011-9511-8","volume":"63","author":"N Bansal","year":"2012","unstructured":"Bansal, N., Gupta, A., Li, J., Mestre, J., Nagarajan, V., Rudra, A.: When LP is the cure for your matching woes: improved bounds for stochastic matchings. Algorithmica 63(4), 733\u2013762 (2012)","journal-title":"Algorithmica"},{"issue":"1","key":"26_CR6","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1109\/TIT.2011.2169296","volume":"58","author":"G Bellala","year":"2012","unstructured":"Bellala, G., Bhavnani, S.K., Scott, C.: Group-based active query selection for rapid diagnosis in time-critical situations. IEEE Trans. Inf. Theor. 58(1), 459\u2013478 (2012)","journal-title":"IEEE Trans. Inf. Theor."},{"key":"26_CR7","doi-asserted-by":"crossref","unstructured":"Blum, A., Chalasani, P., Coppersmith, D., Pulleyblank, W.R., Raghavan, P., Sudan, M.: The minimum latency problem. In: STOC, pp. 163\u2013171 (1994)","DOI":"10.1145\/195058.195125"},{"issue":"2","key":"26_CR8","doi-asserted-by":"crossref","first-page":"15","DOI":"10.1145\/1921659.1921661","volume":"7","author":"VT Chakaravarthy","year":"2011","unstructured":"Chakaravarthy, V.T., Pandit, V., Roy, S., Awasthi, P., Mohania, M.K.: Decision trees for entity identification: approximation algorithms and hardness results. ACM Trans. Algorithms 7(2), 15 (2011)","journal-title":"ACM Trans. Algorithms"},{"key":"26_CR9","doi-asserted-by":"crossref","unstructured":"Chaudhuri, K., Godfrey, B., Rao, S., Talwar, K.: Paths, trees, and minimum latency tours. In: FOCS, pp. 36\u201345 (2003)","DOI":"10.1109\/SFCS.2003.1238179"},{"key":"26_CR10","unstructured":"Cicalese, F., Laber, E.S., Saettler, A.M.: Diagnosis determination: decision trees optimizing simultaneously worst and expected testing cost. In: ICML, pp. 414\u2013422 (2014)"},{"key":"26_CR11","unstructured":"Dasgupta, S.: Analysis of a greedy active learning strategy. In: NIPS (2004)"},{"issue":"4","key":"26_CR12","doi-asserted-by":"crossref","first-page":"945","DOI":"10.1287\/moor.1080.0330","volume":"33","author":"BC Dean","year":"2008","unstructured":"Dean, B.C., Goemans, M.X., Vondr\u00e1k, J.: Approximating the stochastic knapsack problem: the benefit of adaptivity. Math. Oper. Res. 33(4), 945\u2013964 (2008)","journal-title":"Math. Oper. Res."},{"issue":"4","key":"26_CR13","doi-asserted-by":"crossref","first-page":"634","DOI":"10.1145\/285055.285059","volume":"45","author":"U Feige","year":"1998","unstructured":"Feige, U.: A threshold of ln n for approximating set cover. J. ACM 45(4), 634\u2013652 (1998)","journal-title":"J. ACM"},{"key":"26_CR14","first-page":"427","volume":"42","author":"D Golovin","year":"2011","unstructured":"Golovin, D., Krause, A.: Adaptive submodularity: theory and applications in active learning and stochastic optimization. J. Artif. Intell. Res. 42, 427\u2013486 (2011)","journal-title":"J. Artif. Intell. Res."},{"key":"26_CR15","unstructured":"Golovin, D., Krause, A., Ray, D.: Near-optimal Bayesian active learning with noisy observations. In: NIPS, pp. 766\u2013774 (2010)"},{"key":"26_CR16","unstructured":"Grammel, N., Hellerstein, L., Kletenik, D., Lin, P.: Scenario submodular cover. CoRR abs\/1603.03158 (2016). (to appear in WAOA 2016)"},{"key":"26_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"141","DOI":"10.1007\/978-3-642-04414-4_15","volume-title":"Algorithmic Learning Theory","author":"A Guillory","year":"2009","unstructured":"Guillory, A., Bilmes, J.: Average-case active learning with costs. In: Gavald\u00e0, R., Lugosi, G., Zeugmann, T., Zilles, S. (eds.) ALT 2009. LNCS, vol. 5809, pp. 141\u2013155. Springer, Heidelberg (2009). doi: 10.1007\/978-3-642-04414-4_15"},{"key":"26_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"690","DOI":"10.1007\/978-3-642-14165-2_58","volume-title":"Automata, Languages and Programming","author":"A Gupta","year":"2010","unstructured":"Gupta, A., Nagarajan, V., Ravi, R.: Approximation algorithms for optimal decision trees and adaptive TSP problems. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6198, pp. 690\u2013701. Springer, Heidelberg (2010). doi: 10.1007\/978-3-642-14165-2_58"},{"issue":"4","key":"26_CR19","first-page":"19","volume":"5","author":"FM Harper","year":"2015","unstructured":"Harper, F.M., Konstan, J.A.: The movielens datasets: history and context. ACM Trans. Interact. Intell. Syst. (TiiS) 5(4), 19 (2015)","journal-title":"ACM Trans. Interact. Intell. Syst. (TiiS)"},{"key":"26_CR20","doi-asserted-by":"crossref","unstructured":"Hyafil, L., Rivest, R.L.: Constructing optimal binary decision trees is $$NP$$ -complete. Inf. Process. Lett. 5(1), 15\u201317 (1976\/1977)","DOI":"10.1016\/0020-0190(76)90095-8"},{"key":"26_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/978-3-642-31594-7_41","volume-title":"Automata, Languages, and Programming","author":"S Im","year":"2012","unstructured":"Im, S., Nagarajan, V., Zwaan, R.: Minimum latency submodular cover. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012. LNCS, vol. 7391, pp. 485\u2013497. Springer, Heidelberg (2012). doi: 10.1007\/978-3-642-31594-7_41"},{"issue":"1\u20132","key":"26_CR22","first-page":"377","volume":"145","author":"S Im","year":"2014","unstructured":"Im, S., Sviridenko, M., van der Zwaan, R.: Preemptive and non-preemptive generalized min sum set cover. Math. Program. 145(1\u20132), 377\u2013401 (2014)","journal-title":"Math. Program."},{"key":"26_CR23","unstructured":"Javdani, S., Chen, Y., Karbasi, A., Krause, A., Bagnell, D., Srinivasa, S.S.: Near optimal bayesian active learning for decision making. In: AISTATS, pp. 430\u2013438 (2014)"},{"key":"26_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/3-540-48447-7_17","volume-title":"Algorithms and Data Structures","author":"SR Kosaraju","year":"1999","unstructured":"Kosaraju, S.R., Przytycka, T.M., Borgstrom, R.: On an optimal split tree problem. In: Dehne, F., Sack, J.-R., Gupta, A., Tamassia, R. (eds.) WADS 1999. LNCS, vol. 1663, pp. 157\u2013168. Springer, Heidelberg (1999). doi: 10.1007\/3-540-48447-7_17"},{"key":"26_CR25","doi-asserted-by":"crossref","unstructured":"Navidi, F., Kambadur, P., Nagarajan, V.: Adaptive submodular ranking. arXiv preprint arXiv:1606.01530 (2016)","DOI":"10.1007\/978-3-319-59250-3_26"},{"issue":"6","key":"26_CR26","doi-asserted-by":"crossref","first-page":"433","DOI":"10.1016\/j.orl.2011.08.002","volume":"39","author":"M Skutella","year":"2011","unstructured":"Skutella, M., Williamson, D.P.: A note on the generalized min-sum set cover problem. Oper. Res. Lett. 39(6), 433\u2013436 (2011)","journal-title":"Oper. Res. Lett."},{"issue":"4","key":"26_CR27","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1007\/BF02579435","volume":"2","author":"L Wolsey","year":"1982","unstructured":"Wolsey, L.: An analysis of the greedy algorithm for the submodular set covering problem. Combinatorica 2(4), 385\u2013393 (1982)","journal-title":"Combinatorica"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-59250-3_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,9,24]],"date-time":"2019-09-24T19:50:08Z","timestamp":1569354608000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-59250-3_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319592497","9783319592503"],"references-count":27,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-59250-3_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}