Michal Černý and Milan Hladík. Two complexity results on c-optimality in experimental design. Comput. Optim. Appl., 51(3):1397–1408, 2012.
[PDF] [gzipped postscript] [postscript] [HTML]
Finding a c-optimal design of a regression model is a basic optimization problem in statistics. We study the computational complexity of the problem in the case of a finite experimental domain. We formulate a decision version of the problem and prove its -completeness. We provide examples of computationally complex instances of the design problem, motivated by cryptography. The problem, being -complete, is then relaxed; we prove that a decision version of the relaxation, called approximate c-optimality, is P-complete. We derive an equivalence theorem for linear programming: we show that the relaxed c-optimality is equivalent (in the sense of many-one LOGSPACE-reducibility) to general linear programming.
@article{CerHla2012a,
author = "Michal {\v{C}}ern\'{y} and Milan Hlad\'{\i}k",
title = "Two complexity results on c-optimality in experimental design",
journal = "Comput. Optim. Appl.",
fjournal = "Computational Optimization and Applications",
volume = "51",
number = "3",
pages = "1397-1408",
year = "2012",
doi = "10.1007/s10589-010-9377-8",
url = "https://doi.org/10.1007/s10589-010-9377-8",
bib2html_dl_html = "https://link.springer.com/article/10.1007/s10589-010-9377-8",
bib2html_dl_pdf = "https://rdcu.be/cnoU6",
abstract = "Finding a c-optimal design of a regression model is a basic optimization problem in statistics. We study the computational complexity of the problem in the case of a finite experimental domain. We formulate a decision version of the problem and prove its -completeness. We provide examples of computationally complex instances of the design problem, motivated by cryptography. The problem, being -complete, is then relaxed; we prove that a decision version of the relaxation, called approximate c-optimality, is P-complete. We derive an equivalence theorem for linear programming: we show that the relaxed c-optimality is equivalent (in the sense of many-one LOGSPACE-reducibility) to general linear programming.",
keywords = "linear programming, optimal design, {NP}-completeness, {P}-completeness",
issn = "0926-6003",
}
Generated by bib2html.pl (written by Patrick Riley ) on Wed Oct 23, 2024 08:16:44