Jaromír Antoch, Michal Černý, and Milan Hladík. On computational complexity of construction of c-optimal linear regression models over finite experimental domains. Tatra Mt. Math. Publ., 51:11–21, 2012.
[PDF] [gzipped postscript] [postscript] [HTML]
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.
@article{AntCer2012a,
author = "Jarom\'{\i}r Antoch and Michal {\v{C}}ern\'{y} and Milan Hlad\'{\i}k",
title = "On computational complexity of construction of $c$-optimal linear regression models over finite experimental domains",
webtitle = "On computational complexity of construction of <i>c</i>-optimal linear regression models over finite experimental domains",
journal = "Tatra Mt. Math. Publ.",
fjournal = "Tatra Mountains Mathematical Publications",
pages = "11-21",
volume = "51",
year = "2012",
doi = "10.2478/v10127-012-0002-3",
bib2html_dl_pdf = "http://tatra.mat.savba.sk/Full/51/02-a-c-h.pdf",
bib2html_dl_html = "http://tatra.mat.savba.sk/",
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.",
keywords = "optimal design, c-optimality, P-completeness, parallel computation, linear programming, SAC algorithm",
}
Generated by bib2html.pl (written by Patrick Riley ) on Wed Oct 23, 2024 08:16:44