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.
@article{158,
title = {On computational complexity of construction of $c$-optimal linear regression models over finite experimental domains},
journal = {Tatra Mountains Mathematical Publications},
volume = {51},
year = {2012},
doi = {10.2478/tatra.v51i1.158},
language = {EN},
url = {http://dml.mathdoc.fr/item/158}
}
Antoch, Jaromír; Černý, Michal; Hladík, Milan. On computational complexity of construction of $c$-optimal linear regression models over finite experimental domains. Tatra Mountains Mathematical Publications, Tome 51 (2012) . doi : 10.2478/tatra.v51i1.158. http://gdmltest.u-ga.fr/item/158/