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

Rok, strany: 2012, 11 - 21

Recent complexity-theoretic results on finding $\bs{c}$-optimal designs over finite experimental domain $\mathcal{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 $\bs{c}$-optimality does not have an efficient parallel implementation. Further, we study the question whether for finding the $\bs{c}$-optimal designs over finite experimental domain $\mathcal{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 $\bs{c}$-optimality.

ISO 690:

Antoch, J., Hladík, M., Černý, M. 2012. On computational complexity of construction of $c$-optimal linear regression models over finite experimental domains. In Tatra Mountains Mathematical Publications, vol. 51, no.1, pp. 11-21. 1210-3195.

APA:

Antoch, J., Hladík, M., Černý, M. (2012). On computational complexity of construction of $c$-optimal linear regression models over finite experimental domains. Tatra Mountains Mathematical Publications, 51(1), 11-21. 1210-3195.