A Polynomial-Time Approximation Scheme for Sequential Batch Testing of Series Systems

References

• Allen SR, Hellerstein L, Kletenik D, Ünlüyurt T (2017) Evaluation of monotone DNF formulas. Algorithmica 77(3):661–685.Crossref, Google Scholar
• Ben-Dov Y (1981) Optimal testing procedures for special structures of coherent systems. Management Sci. 27(12):1410–1420.Link, Google Scholar
• Berend D, Brafman R, Cohen S, Shimony SE, Zucker S (2014) Optimal ordering of independent tests with precedence constraints. Discrete Appl. Math. 162:115–127.Crossref, Google Scholar
• Boros E, Ünlüyurt T (2000) Sequential testing of series-parallel systems of small depth. Laguna M, Velarde JLG, eds. Computing Tools for Modeling, Optimization and Simulation, Operations Research/Computer Science Interfaces Series, vol. 12 (Springer, Boston), 39–73.Google Scholar
• Butterworth R (1972) Some reliability fault-testing models. Oper. Res. 20(2):335–343.Link, Google Scholar
• Chang MF, Shi W, Fuchs WK (1990) Optimal diagnosis procedures for k-out-of-n structures. IEEE Trans. Comput. 39(4):559–564.Crossref, Google Scholar
• Chekuri C, Khanna S (2005) A polynomial time approximation scheme for the multiple knapsack problem. SIAM J. Comput. 35(3):713–728.Crossref, Google Scholar
• Cox LA, Yuping Q, Kuehner W (1989) Heuristic least-cost computation of discrete classification functions with uncertain argument values. Ann. Oper. Res. 21(1):1–29.Crossref, 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
• De Reyck B, Leus R (2008) R&D project scheduling when activities may fail. IIE Trans. 40(4):367–384.Crossref, Google Scholar
• Deshpande A, Hellerstein L, Kletenik D (2014) Approximation algorithms for stochastic Boolean function evaluation and stochastic submodular set cover. Chekuri C, ed. Proc. 25th Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1453–1467.Google Scholar
• Duffuaa S, Raouf A (1990) An optimal sequence in multicharacteristics inspection. J. Optim. Theory Appl. 67(1):79–86.Crossref, Google Scholar
• Garey MR (1973) Optimal task sequencing with precedence constraints. Discrete Math. 4(1):37–56.Crossref, Google Scholar
• Greiner R, Hayward R, Jankowska M, Molloy M (2006) Finding optimal satisficing strategies for and-or trees. Artificial Intelligence 170(1):19–58.Crossref, Google Scholar
• Gupta A, Nagarajan V, Ravi R (2016) Robust and maxmin optimization under matroid and knapsack uncertainty sets. ACM Trans. Algorithms 12(1):10:1–10:21.Google Scholar
• Kaplan H, Kushilevitz E, Mansour Y (2005) Learning with attribute costs. Proc. 37th Annual ACM Sympos. Theor. Comput. (Association for Computing Machinery, New York), 356–365.Google Scholar
• Kellerer H, Pferschy U (1999) A new fully polynomial time approximation scheme for the knapsack problem. J. Combinatorial Optim. 3(1):59–71.Crossref, Google Scholar
• Mitten L (1960) An analytic solution to the least cost testing sequence problem. J. Indust. Engrg. 11(1):17.Google Scholar
• Moret BM (1982) Decision trees and diagrams. ACM Comput. Surv. 14(4):593–623.Crossref, Google Scholar
• Natarajan K (1986) Optimizing depth-first search of AND-OR trees. Research Report RC-11842, IBM T. J. Watson Research Center, Yorktown Heights, NY.bookGoogle Scholar
• Nilsson NJ (1971) Problem-Solving Methods in Artificial Intelligence (McGraw-Hill, New York).Google Scholar
• Qiu Y, Cox LA Jr, Davis L (1992) Guess-and-verify heuristics for reducing uncertainties in expert classification systems. Dubois D, Wellman MP, D’Ambrosio B, Smets P, eds. Proc. 8th Internat. Conf. Uncertainty Artificial Intelligence (Morgan Kaufmann Publishers, San Francisco), 252–258.Google Scholar
• Simon HA, Kadane JB (1975) Optimal problem-solving search: All-or-none solutions. Artificial Intelligence 6(3):235–247.Crossref, Google Scholar
• Smith DE (1989) Controlling backward inference. Artificial Intelligence 39(2):145–208.Crossref, Google Scholar
• Ünlüyurt T (2004) Sequential testing of complex systems: A review. Discrete Appl. Math. 142(1):189–205.Crossref, Google Scholar