Nonadaptive Stochastic Score Classification and Explainable Half-Space Evaluation

References

• Allen S, Hellerstein L, Kletenik D, Ünlüyurt T (2017) Evaluation of monotone DNF formulas. Algorithmica 77(3):661–685.Crossref, Google Scholar
• Austin J, Ocker R, Bhati A (2010) Kentucky pretrial risk assessment instrument validation. Report, Bureau of Justice Statistics, Washington, DC.Google Scholar
• Bansal N, Nagarajan V (2015) On the adaptivity gap of stochastic orienteering. Math. Programming 154(1–2):145–172.Crossref, Google Scholar
• Bansal N, Gupta A, Li J, Mestre J, Nagarajan V, Rudra A (2012) When LP is the cure for your matching woes: Improved bounds for stochastic matchings. Algorithmica 63(4):733–762.Crossref, Google Scholar
• Behnezhad S, Derakhshan M, Hajiaghayi M (2020) Stochastic matching with few queries: (1-ϵ) approximation. Proc. 52nd Annual ACM SIGACT Sympos. Theory Comput. (Association for Computing Machinery, New York), 1111–1124.Google Scholar
• Ben-Dov Y (1981) Optimal testing procedures for special structures of coherent systems. Management Sci. 27(12):1410–1420.Link, Google Scholar
• Beneish MD, Lee CM, Nichols DC (2013) Earnings manipulation and expected returns. Financial Anal. J. 69(2):57–82.Crossref, Google Scholar
• Bhalgat A, Goel A, Khanna S (2011) Improved approximation results for stochastic knapsack problems. Proc. Twenty-Second Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (Society for Industrial and Applied Mathematics, Philadelphia), 1647–1665.Google Scholar
• Blanc G, Lange J, Tan LY (2021) Query strategies for priced information, revisited. Proc. Thirty-Second Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (Society for Industrial and Applied Mathematics, Philadelphia), 1638–1650.Google Scholar
• Butterworth R (1972) Some reliability fault-testing models. Oper. Res. 20(2):335–343.Link, Google Scholar
• Daldal R, Gamzu I, Segev D, Ünlüyurt T (2016) Approximation algorithms for sequential batch-testing of series systems. Naval Res. Logist. 63(4):275–286.Crossref, Google Scholar
• Daldal R, Özlük Ö, Selçuk B, Shahmoradi Z, Ünlüyurt T (2017) Sequential testing in batches. Ann. Oper. Res. 253(1):97–116.Crossref, Google Scholar
• Dean BC, Goemans MX, Vondrák J (2008) Approximating the stochastic knapsack problem: The benefit of adaptivity. Math. Oper. Res. 33(4):945–964.Link, Google Scholar
• Deshpande A, Hellerstein L, Kletenik D (2016) Approximation algorithms for stochastic submodular set cover with applications to Boolean function evaluation and min-knapsack. ACM Trans. Algorithms 12(3):42.Crossref, Google Scholar
• Ene A, Nagarajan V, Saket R (2017) Approximation algorithms for stochastic k-TSP. 37th IARCS Annual Conf. Foundations Software Tech. Theoret. Comput. Sci. (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany), 27:1–27:14.Google Scholar
• Gage BF, Waterman AD, Shannon W, Boechler M, Rich MW, Radford MJ (2001) Validation of clinical classification schemes for predicting stroke: Results from the national registry of atrial fibrillation. J. Amer. Medical Assoc. 285(22):2864–2870.Crossref, Google Scholar
• Gkenosis D, Grammel N, Hellerstein L, Kletenik D (2018) The stochastic score classification problem. 26th Annual Eur. Sympos. Algorithms (ESA) (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Wadern, Germany), 36:1–36:14.Google Scholar
• Golovin D, Krause A (2017) Adaptive submodularity: A new approach to active learning and stochastic optimization. Preprint, submitted December 6, https://arxiv.org/abs/1003.3967.Google Scholar
• Grammel N, Hellerstein L, Kletenik D, Liu N (2022) Algorithms for the unit-cost stochastic score classification problem. Algorithmica 84(10):3054–3074.Crossref, Google Scholar
• Guha S, Munagala K (2009) Multi-armed bandits with metric switching costs. 36th Internat. Colloquium Automata Languages Programming (ICALP) (Springer, Berlin, Heidelberg), 496–507.Google Scholar
• Gupta A, Nagarajan V (2013) A stochastic probing problem with applications. 16th Internat. Conf. Integer Programming Combinatorial Optim. (IPCO) (Springer-Verlag, Berlin, Heidelberg), 205–216.Google Scholar
• Gupta A, Nagarajan V, Singla S (2017) Adaptivity gaps for stochastic probing: Submodular and XOS functions. Proc. Twenty-Eighth Annual ACM-SIAM Sympos. Discrete Algorithms (SODA) (Society for Industrial and Applied Mathematics, Philadelphia), 1688–1702.Google Scholar
• Gupta A, Krishnaswamy R, Nagarajan V, Ravi R (2015) Running errands in time: Approximation algorithms for stochastic orienteering. Math. Oper. Res. 40(1):56–79.Link, Google Scholar
• Im S, Nagarajan V, van der Zwaan R (2016) Minimum latency submodular cover. ACM Trans. Algorithms 13(1):13.Google Scholar
• Jiang H, Li J, Liu D, Singla S (2020) Algorithms and adaptivity gaps for stochastic k-TSP. 11th Innovations Theoret. Comput. Sci. Conf. (ITCS), vol. 151 (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany), 45:1–45:25.Google Scholar
• Jung J, Concannon C, Shroff R, Goel S, Goldstein DG (2020) Simple rules to guide expert classifications. J. Roy. Statist. Soc. Ser. A Statist. Soc. 183(3):771–800.Crossref, Google Scholar
• Kaplan H, Kushilevitz E, Mansour Y (2005) Learning with attribute costs. Proc. Thirty-Seventh Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 356–365.Google Scholar
• Liu N (2022) Two 6-approximation algorithms for the stochastic score classification problem. Preprint, submitted December 5, https://arxiv.org/abs/2212.02370.Google Scholar
• Moret BME (1982) Decision trees and diagrams. ACM Comput. Surveys 14(4):593–623.Crossref, Google Scholar
• Plank BM, Schewior K (2022) Simple algorithms for stochastic score classification with small approximation ratios. Preprint, submitted January 20, https://arxiv.org/abs/2211.14082.Google Scholar
• Segev D, Shaposhnik Y (2022) A polynomial-time approximation scheme for sequential batch testing of series systems. Oper. Res. 70(2):1153–1165.Link, Google Scholar
• Ünlüyurt T (2004) Sequential testing of complex systems: A review. Discrete Appl. Math. 142(1):189–205.Crossref, Google Scholar
• Ustun B, Rudin C (2019) Learning optimized risk scores. J. Machine Learn. Res. 20(150):1–75.Google Scholar
• Zeng J, Ustun B, Rudin C (2017) Interpretable classification models for recidivism prediction. J. Roy. Statist. Soc. Ser. A Statist. Soc. 180(3):689–722.Crossref, Google Scholar