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

Abstract

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.