Milan Hladík's Publications:

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

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.

Download

[PDF] [gzipped postscript] [postscript] [HTML] 

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.

BibTeX

@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 Feb 07, 2024 09:31:18