Two complexity results on c-optimality in experimental design |
| |
Authors: | Michal ?erny and Milan Hladík |
| |
Institution: | (1) University of Almer?a, Edificio CITE-III, Ctra. Sacramento s/n, La Ca?ada de San Urbano, 04120 Almer?a, Spain;(2) Facultad de Ciencias, University of Salamanca, Pl. de los Ca?dos s/n, 37.008 Salamanca, Spain |
| |
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 NP\boldsymbol{\mathit{NP}}-completeness. We provide examples of computationally complex instances of the design problem, motivated by cryptography.
The problem, being NP\boldsymbol{\mathit{NP}}-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: | |
本文献已被 SpringerLink 等数据库收录! |
|