<abstract xmlns="http://www.w3.org/1999/xhtml"><p> 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.</p></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.

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

Charles University of Prague Department of Probability and Mathematical Statistics Sokolovsk´a 83 CZ–186-75 Prague 8 CZECH REPUBLIC

University of Economics Prague Department of Econometrics Winston Churchill Square 4 CZ–130-67 Prague CZECH REPUBLIC

Charles University of Prague Department of Applied Mathematics Malostransk´e n´amˇest´ı 25 CZ–118-00 Prague 1 CZECH REPUBLIC

Tatra Mountains Mathematical Publications

Recent complexity-theoretic results on finding c-optimal designs over finite experimental domain X are discussed and their implications for the analysis of...

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

Published Online: Nov 13, 2012

Page range: 11 - 21

DOI: https://doi.org/10.2478/v10127-012-0002-3

Keywords
optimal design, c-optimality, P-completeness, parallel computation, linear programming, SAC algorithm

This content is open access.

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

Published Online: Nov 13, 2012

Page range: 11 - 21

DOI: https://doi.org/10.2478/v10127-012-0002-3

Keywordsoptimal design, c-optimality, P-completeness, parallel computation, linear programming, SAC algorithm

This content is open access.

Keywords
optimal design, c-optimality, P-completeness, parallel computation, linear programming, SAC algorithm