# Approximation Algorithms for D-optimal Design

arXiv: https://arxiv.org/abs/1802.08372 · HTML: https://mlsanity.com/paper/1802.08372/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Feb 2018.

## Built on by (most cited first, 7 of 7)

- [A new perspective on low-rank optimization](https://mlsanity.com/paper/2105.05947/) (2021)
- [What Data Enables Optimal Decisions? An Exact Characterization for Linear Optimization](https://mlsanity.com/paper/2505.21692/) (2025)
- [Experimental Design for Any p-Norm](https://mlsanity.com/paper/2305.01942/) (2023)
- [Fast Screening Rules for Optimal Design via Quadratic Lasso Reformulation](https://mlsanity.com/paper/2310.08939/) (2023)
- [Experimental Design Using Interlacing Polynomials](https://mlsanity.com/paper/2410.11390/) (2024)
- [Spectral Certificates and Projection-DPP Rounding for Determinantal MAP Selection](https://mlsanity.com/paper/2606.19411/) (2026)
- [Fair Multi-View Determinantal Coresets via Adaptive NEPv](https://mlsanity.com/paper/2608.18181/) (2026)

## Abstract (arXiv)

Experimental design is a classical statistics problem and its aim is to estimate an unknown m-dimensional 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, denoted as hatβ. In this paper, we will study one of the most robust measures of error estimation - D-optimality criterion, which corresponds to minimizing the volume of the confidence ellipsoid for the estimation error β-hatβ. 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 frac1e-approximation for the D-optimal 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 (1-ε)-approximation if k≥ frac4mε+frac12ε2log(frac1ε) for any ε ∈ (0,1). Finally, for D-optimal design with repetitions, we study a different algorithm proposed by literature and show that it can improve this asymptotic approximation ratio.