{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T14:26:23Z","timestamp":1772807183526,"version":"3.50.1"},"reference-count":22,"publisher":"Springer Science and Business Media LLC","issue":"10","license":[{"start":{"date-parts":[[2022,7,11]],"date-time":"2022-07-11T00:00:00Z","timestamp":1657497600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2022,7,11]],"date-time":"2022-07-11T00:00:00Z","timestamp":1657497600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1217968"],"award-info":[{"award-number":["IIS-1217968"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["IIS-1909335"],"award-info":[{"award-number":["IIS-1909335"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"The Professional Staff Congress and The City University of New York"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2022,10]]},"DOI":"10.1007\/s00453-022-00982-4","type":"journal-article","created":{"date-parts":[[2022,7,12]],"date-time":"2022-07-12T12:05:56Z","timestamp":1657627556000},"page":"3054-3074","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Algorithms for the Unit-Cost Stochastic Score Classification Problem"],"prefix":"10.1007","volume":"84","author":[{"given":"Nathaniel","family":"Grammel","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3743-7965","authenticated-orcid":false,"given":"Lisa","family":"Hellerstein","sequence":"additional","affiliation":[]},{"given":"Devorah","family":"Kletenik","sequence":"additional","affiliation":[]},{"given":"Naifeng","family":"Liu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,7,11]]},"reference":[{"key":"982_CR1","doi-asserted-by":"publisher","unstructured":"Acharya, J., Jafarpour, A., Orlitsky, A.: Expected query complexity of symmetric Boolean functions. In: IEEE 49th Annual Allerton Conference on Communication, Control, and Computing, pp. 26\u201329 (2011). https:\/\/doi.org\/10.1109\/Allerton.2011.6120145","DOI":"10.1109\/Allerton.2011.6120145"},{"key":"982_CR2","doi-asserted-by":"publisher","unstructured":"Ben-Dov, Y.: Optimal testing procedure for special structures of coherent systems. Management Science (1981). https:\/\/doi.org\/10.1287\/mnsc.27.12.1410","DOI":"10.1287\/mnsc.27.12.1410"},{"issue":"1\u20134","key":"982_CR3","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1023\/A:1018958928835","volume":"26","author":"E Boros","year":"1999","unstructured":"Boros, E., \u00dcnl\u00fcyurt, T.: Diagnosing double regular systems. Ann. Math. Artif. Intell. 26(1\u20134), 171\u2013191 (1999). https:\/\/doi.org\/10.1023\/A:1018958928835","journal-title":"Ann. Math. Artif. Intell."},{"issue":"4","key":"982_CR4","doi-asserted-by":"publisher","first-page":"559","DOI":"10.1109\/12.54850","volume":"39","author":"MF Chang","year":"1990","unstructured":"Chang, M.F., Shi, W., Fuchs, W.K.: Optimal diagnosis procedures for $$k$$-out-of-$$n$$ structures. IEEE Trans. Comput. 39(4), 559\u2013564 (1990). https:\/\/doi.org\/10.1109\/12.54850","journal-title":"IEEE Trans. Comput."},{"key":"982_CR5","doi-asserted-by":"publisher","unstructured":"Das, H., Jafarpour, A., Orlitsky, A., Pan, S., Suresh, A.T.: On the query computation and verification of functions. In: IEEE International symposium on information theory (ISIT), pp. 2711\u20132715 (2012). https:\/\/doi.org\/10.1109\/ISIT.2012.6284010","DOI":"10.1109\/ISIT.2012.6284010"},{"key":"982_CR6","doi-asserted-by":"publisher","DOI":"10.1145\/2876506","author":"A Deshpande","year":"2016","unstructured":"Deshpande, A., Hellerstein, L., Kletenik, D.: Approximation algorithms for stochastic submodular set cover with applications to boolean function evaluation and min-knapsack. ACM Trans. Algorith. (2016). https:\/\/doi.org\/10.1145\/2876506","journal-title":"ACM Trans. Algorith."},{"key":"982_CR7","doi-asserted-by":"publisher","unstructured":"Ghuge, R., Gupta, A., Nagarajan, V.: Non-adaptive stochastic score classification and explainable halfspace evaluation. CoRR (2021). https:\/\/doi.org\/10.48550\/arXiv.2111.05687","DOI":"10.48550\/arXiv.2111.05687"},{"key":"982_CR8","doi-asserted-by":"publisher","unstructured":"Gkenosis, D., Grammel, N., Hellerstein, L., Kletenik, D.: The stochastic score classification problem. In: Azar, Y., Bast, H., Herman, G. (eds.) 26th Annual european symposium on algorithms (ESA 2018), Leibniz international proceedings in informatics (LIPIcs), vol. 112, pp. 36:1\u201336:14. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2018). https:\/\/doi.org\/10.4230\/LIPIcs.ESA.2018.36. http:\/\/drops.dagstuhl.de\/opus\/volltexte\/2018\/9499","DOI":"10.4230\/LIPIcs.ESA.2018.36"},{"key":"982_CR9","doi-asserted-by":"publisher","first-page":"269","DOI":"10.1016\/j.dam.2021.12.001","volume":"309","author":"D Gkenosis","year":"2022","unstructured":"Gkenosis, D., Grammel, N., Hellerstein, L., Kletenik, D.: The stochastic boolean function evaluation problem for symmetric boolean functions. Discret. Appl. Math. 309, 269\u2013277 (2022). https:\/\/doi.org\/10.1016\/j.dam.2021.12.001","journal-title":"Discret. Appl. Math."},{"issue":"1","key":"982_CR10","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.artint.2005.09.002","volume":"170","author":"R Greiner","year":"2006","unstructured":"Greiner, R., Hayward, R., Jankowska, M., Molloy, M.: Finding optimal satisficing strategies for and-or trees. Artif. Intell. 170(1), 19\u201358 (2006). https:\/\/doi.org\/10.1016\/j.artint.2005.09.002","journal-title":"Artif. Intell."},{"key":"982_CR11","doi-asserted-by":"publisher","unstructured":"Gupta, A., Nagarajan, V.: A stochastic probing problem with applications. In: International conference on integer programming and combinatorial optimization, pp. 205\u2013216. Springer (2013). https:\/\/doi.org\/10.1007\/978-3-642-36694-9_18","DOI":"10.1007\/978-3-642-36694-9_18"},{"key":"982_CR12","doi-asserted-by":"crossref","unstructured":"Jung, J., Concannon, C., Shroff, R., Goel, S., Goldstein, D.G.: Simple rules for complex decisions. arXiv\u00a0preprint arXiv:1702.04690 (2017)","DOI":"10.2139\/ssrn.2919024"},{"issue":"4","key":"982_CR13","doi-asserted-by":"publisher","first-page":"639","DOI":"10.1109\/JSAC.2013.130403","volume":"31","author":"H Kowshik","year":"2013","unstructured":"Kowshik, H., Kumar, P.: Optimal computation of symmetric boolean functions in collocated networks. IEEE J. Select. Area. Commun. 31(4), 639\u2013654 (2013). https:\/\/doi.org\/10.1109\/JSAC.2013.130403","journal-title":"IEEE J. Select. Area. Commun."},{"key":"982_CR14","unstructured":"Salloum, S.: Optimal testing algorithms for symmetric coherent systems. Ph.D. thesis, University of Southern California (1979)"},{"key":"982_CR15","doi-asserted-by":"publisher","unstructured":"Salloum, S., Breuer, M.: An optimum testing algorithm for some symmetric coherent systems. J. Math. Anal. Appl. 101(1), 170\u2013194 (1984). https:\/\/doi.org\/10.1016\/0022-247X(84)90064-7","DOI":"10.1016\/0022-247X(84)90064-7"},{"issue":"2","key":"982_CR16","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1109\/24.589958","volume":"46","author":"S Salloum","year":"1997","unstructured":"Salloum, S., Breuer, M.A.: Fast optimal diagnosis procedures for k-out-of-n:g systems. IEEE Trans. Reliabil. 46(2), 283\u2013290 (1997). https:\/\/doi.org\/10.1109\/24.589958","journal-title":"IEEE Trans. Reliabil."},{"key":"982_CR17","doi-asserted-by":"publisher","unstructured":"Singla, S.: The price of information in combinatorial optimization. In: Proceedings of the twenty-ninth annual ACM-SIAM symposium on discrete algorithms, pp. 2523\u20132532. SIAM (2018). https:\/\/doi.org\/10.1137\/1.9781611975031.161","DOI":"10.1137\/1.9781611975031.161"},{"key":"982_CR18","unstructured":"Tran, T., Luo, W., Phung, D., Morris, J., Rickard, K., Venkatesh, S.: Preterm birth prediction: Deriving stable and interpretable rules from high dimensional data. In: Conference on machine learning in healthcare, LA, USA (2016)"},{"issue":"1\u20133","key":"982_CR19","doi-asserted-by":"publisher","first-page":"189","DOI":"10.1016\/j.dam.2002.08.001","volume":"142","author":"T \u00dcnl\u00fcyurt","year":"2004","unstructured":"\u00dcnl\u00fcyurt, T.: Sequential testing of complex systems: a review. Discret. Appl. Math. 142(1\u20133), 189\u2013205 (2004). https:\/\/doi.org\/10.1016\/j.dam.2002.08.001","journal-title":"Discret. Appl. Math."},{"issue":"3","key":"982_CR20","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/s10994-015-5528-6","volume":"102","author":"B Ustun","year":"2016","unstructured":"Ustun, B., Rudin, C.: Supersparse linear integer models for optimized medical scoring systems. Mach. Learn. 102(3), 349\u2013391 (2016). https:\/\/doi.org\/10.1007\/s10994-015-5528-6","journal-title":"Mach. Learn."},{"key":"982_CR21","doi-asserted-by":"publisher","unstructured":"Ustun, B., Rudin, C.: Optimized risk scores. In: Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining, pp. 1125\u20131134. ACM (2017). https:\/\/doi.org\/10.1145\/3097983.3098161","DOI":"10.1145\/3097983.3098161"},{"issue":"3","key":"982_CR22","doi-asserted-by":"publisher","first-page":"689","DOI":"10.1111\/rssa.12227","volume":"180","author":"J Zeng","year":"2017","unstructured":"Zeng, J., Ustun, B., Rudin, C.: Interpretable classification models for recidivism prediction. J. Royal Stat. Soci.: Seri. A (Stat. Soci.) 180(3), 689\u2013722 (2017). https:\/\/doi.org\/10.1111\/rssa.12227","journal-title":"J. Royal Stat. Soci.: Seri. A (Stat. Soci.)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00982-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-00982-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-00982-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,30]],"date-time":"2022-09-30T14:20:23Z","timestamp":1664547623000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-00982-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,11]]},"references-count":22,"journal-issue":{"issue":"10","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["982"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-00982-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,11]]},"assertion":[{"value":"26 June 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 April 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 July 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}