  


Approximation Algorithms for Doptimal Design
Mohit Singh (mohitsinghrgmail.com) Abstract: Experimental design is a classical statistics problem and its aim is to estimate an unknown mdimensional vector from linear measurements where a Gaussian noise is introduced in each measurement. For the combinatorial experimental design problem, the goal is to pick k out of the given n experiments so as to make the most accurate estimate of the unknown parameters. In this paper, we will study one of the most robust measures of error estimation  Doptimality criterion, which corresponds to minimizing the volume of the confidence ellipsoid for the estimation error. The problem gives rise to two natural variants depending on whether repetitions of experiments are allowed or not. We first propose an approximation algorithm with a 1/e approximation for the Doptimal design problem with and without repetitions, giving the first constant factor approximation for the problem. We then analyze another sampling approximation algorithm and prove that it is asymptotically optimal when k/m goes to infinity. Finally, for Doptimal design with repetitions, we study a different algorithm proposed by literature and show that it can improve this asymptotic approximation ratio. Keywords: Doptimal Design; approximation algorithm; determinant; derandomization Category 1: Combinatorial Optimization Citation: Submitted Download: [PDF] Entry Submitted: 03/08/2018 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  