On computational complexity of construction of c -optimal linear regression models over finite experimental domains

Antoch, Jaromír; Černý, Michal; Hladík, Milan

doi:10.2478/v10127-012-0002-3

Abstract

Recent complexity-theoretic results on finding c-optimal designs over finite experimental domain X are discussed and their implications for the analysis of existing algorithms and for the construction of new algorithms are shown. Assuming some complexity-theoretic conjectures, we show that the approximate version of c-optimality does not have an efficient parallel implementation. Further, we study the question whether for finding the c-optimal designs over finite experimental domain X there exist a strongly polynomial algorithms and show relations between considered design problem and linear programming. Finally, we point out some complexity-theoretic properties of the SAC algorithm for c-optimality.

References

[1] ARORA, S.-BARAK, B.: Computational Complexity. A Modern Approach. Cambridge University Press, Cambridge, 2009.10.1017/CBO9780511804090
Search in Google Scholar
[2] ATKINSON, A.-DONEV, A.-TOBIAS, R.: Optimum Experimental Designs with SAS. Oxford University Press, Oxford, 2007.
Search in Google Scholar
[3] ˇC ERN´Y, M.-HLAD´IK, M.: Two complexity results on c-optimality in experimental design, Computational Optimization and Applications 51 2012, 1397-1408, http://www.springerlink.com/content/115ttx6lu150434k/fulltext.pdf10.1007/s10589-010-9377-8
Search in Google Scholar
[4] ˇC ERN´Y, M.-HLAD´IK, M.-SKOˇCDOPOLOV´A, V.: On computationally complex in- stances of the c-optimal experimental design problem: Breaking RSA-based cryptography via c-optimal designs, in: Proc. of 19th Internat. Conference on Comput. Statist.- -CompStat ’10 (Y. Lechevallier, G. Saporta, eds.), Paris, France, Physica Verlag, Heidel- berg, 2010, pp. 879-886.
Search in Google Scholar
[5] EDMONDS, J.: Systems of distinct representatives and linear algebra, J. Res. Natl. Bur. Stand., Sec. B 71B (1967), 241-245.10.6028/jres.071B.033
Search in Google Scholar
[6] GREENLAW, R.-HOOVER, H.-RUZZO, W.: Limits to Parallel Computation. P-completeness Theory. Oxford University Press, Oxford, 1995.10.1093/oso/9780195085914.001.0001
Search in Google Scholar
[7] HARMAN, R.-JUR´IK, T.: Computing c-optimal experimental designs using the simplex method of linear programming, Comput. Statist. Data Anal. 53 (2008), 247-254.10.1016/j.csda.2008.06.023
Search in Google Scholar
[8] KHACHIYAN, L.: A polynomial algorithm for linear programming, Dokl. Akad. Nauk SSSR 244 (1979), No. 5, 1093-1096.
Search in Google Scholar
[9] KLEE, V.-MINTY, G. J.: How good is the simplex algorithm? Inequalities III, in: Proc. of the 3rd Symposium on Inequalities held at the University of California, Los Angeles, Calif., 1969 (O. Shisha, ed.), Academic Press, New York, 1972, pp. 159-175.
Search in Google Scholar
[10] ODIFREDDI, P.: Classical Recursion Theory. Volume I. Stud. Logic Found. Math., Vol. 125, Elsevier, Amsterdam, 1999.
Search in Google Scholar
[11] PAPADIMITRIOU, C.: Computational Complexity. Addison-Wesley, Longman, 1995.
Search in Google Scholar
[12] P´AZMAN, A.: Foundations of Optimum Experimental Design. Reidel Publ. Comp., Dordrecht, 1986.
Search in Google Scholar
[13] PUKELSHEIM, F.-RIEDER, S.: Efficient rounding in approximate designs, Biometrika 79 (1992), 763-770.10.1093/biomet/79.4.763
Search in Google Scholar
[14] RAO, C. R.: Linear Statistical Inference and its Applications. John Wiley & Sons, New York, 1973.10.1002/9780470316436
Search in Google Scholar
[15] ROOS, C.-TERLAKY, T.-VIAL, J.-P.: Interior Point Methods for Linear Optimization . Springer, Heidelberg, 2006.
Search in Google Scholar
[16] SCHRIJVER, A.: Theory of Linear and Integer Programming. John Wiley & Sons, New York, 2000.
Search in Google Scholar
[17] WHITTLE, P.: Some general points in the theory of optimal experimental design, J. Roy. Statist. Soc. Ser. B. 35 (1973), 123-130.
Search in Google Scholar

On computational complexity of construction of c -optimal linear regression models over finite experimental domains

Abstract

Paradigm

My account