Algorithms for Budget-Constrained D-Optimal Design

References

• [1] Ahipaşaoğlu SD (2021) A branch-and-bound algorithm for the exact optimal experimental design problem. Stat. Comput. 31(5):65.Crossref, Google Scholar
• [2] Allen-Zhu Z, Li Y, Singh A, Wang Y (2021) Near-optimal discrete optimization for experimental design: A regret minimization approach. Math. Programming 186:439–478. Crossref, Google Scholar
• [3] Anstreicher KM (2020) Efficient solution of maximum-entropy sampling problems. Oper. Res. 68(6):1826–1835.Link, Google Scholar
• [4] Atkinson A, Donev A, Tobias R (2007) Optimum Experimental Designs, with SAS (Oxford University Press, Oxford, UK).Crossref, Google Scholar
• [5] Bouhtou M, Gaubert S, Sagnol G (2010) Submodularity and randomized rounding techniques for optimal experimental design. Electronic Notes Discrete Math. 36:679–686.Crossref, Google Scholar
• [6] Brown A, Laddha A, Pittu M, Singh M (2022) Efficient determinant maximization for all matroids. Preprint, submitted November 18, https://arxiv.org/abs/2211.10507.Google Scholar
• [7] Coey C, Kapelevich L, Vielma JP (2023) Conic optimization with spectral functions on Euclidean Jordan algebras. Math. Oper. Res. 48(4):1906–1933.Abstract, Google Scholar
• [8] de Aguiar P, Bourguignon B, Khots M, Massart D, Phan-Than-Luu R (1995) D-optimal designs. Chemometrics Intelligent Laboratory Systems 30(2):199–210.Crossref, Google Scholar
• [9] Horel T, Ioannidis S, Muthukrishnan S (2014) Budget feasible mechanisms for experimental design. Pardo A, Viola A, eds. LATIN 2014 Theoret. Informatics (Springer, Berlin), 719–730.Crossref, Google Scholar
• [10] Hou SH (1998) Classroom note: A simple proof of the Leverrier–Faddeev characteristic polynomial algorithm. SIAM Rev. 40(3):706–709.Crossref, Google Scholar
• [11] Huang CC, Kakimura N (2021) Improved streaming algorithms for maximizing monotone submodular functions under a knapsack constraint. Algorithmica 83(3):879–902.Crossref, Google Scholar
• [12] Khakurel S, Yeow T, Saha S, Dhakal R (2023) Post-earthquake building assessments: How long do they take? Bull. New Zealand Soc. Earthquake Engrg. 56(2):115–126.Crossref, Google Scholar
• [13] Ko CW, Lee J, Queyranne M (1995) An exact algorithm for maximum entropy sampling. Oper. Res. 43(4):684–691.Link, Google Scholar
• [14] Lau LC, Zhou H (2022) A local search framework for experimental design. SIAM J. Comput. 51(4):900–951.Crossref, Google Scholar
• [15] Li Y, Xie W (2024) Best principal submatrix selection for the maximum entropy sampling problem: Scalable algorithms and performance guarantees. Oper. Res. 72(2):493–513.Link, Google Scholar
• [16] Li Y, Fampa M, Lee J, Qiu F, Xie W, Yao R (2024) D-optimal data fusion: Exact and approximation algorithms. INFORMS J. Comput. 36(1):97–120.Link, Google Scholar
• [17] Madan V, Nikolov A, Singh M, Tantipongpipat U (2020) Maximizing determinants under matroid constraints. Proc. 61st IEEE Annual Sympos. Foundations Comput. Sci. (Institute of Electrical and Electronics Engineers, Piscataway, NJ), 565–576.Google Scholar
• [18] Madan V, Singh M, Tantipongpipat U, Xie W (2019) Combinatorial algorithms for optimal design. Beygelzimer A, Hsu D, eds. Proc. 32nd Conf. Learn. Theory, Proceedings of Machine Learning Research, vol. 99 (JMLR.org), 2210–2258.Google Scholar
• [19] Mahabadi S, Vuong TD (2022) Composable coresets for constrained determinant maximization and beyond. Preprint, submitted November 1, https://arxiv.org/abs/2211.00289.Google Scholar
• [20] Nikolov A (2015) Randomized rounding for the largest simplex problem. Servedio R, Rubinfeld R, eds. Proc. 47th Annual ACM Sympos. Theory Comput. (Association for Computing Machinery, New York), 861–870.Google Scholar
• [21] Nikolov A, Singh M, Tantipongpipat UT (2022) Proportional volume sampling and approximation algorithms for A-optimal design. Math. Oper. Res. 47(2):847–877.Link, Google Scholar
• [22] Panconesi A, Srinivasan A (1997) Randomized distributed edge coloring via an extension of the Chernoff–Hoeffding bounds. SIAM J. Comput. 26(2):350–368.Crossref, Google Scholar
• [23] Pokhilko V, Zhang Q, Kang L, Mays DP (2019) D-optimal design for network A/B testing. J. Stat. Theory Practice 13(4):61:1–61:23.Crossref, Google Scholar
• [24] Ponte G, Fampa M, Lee J (2025) Branch-and-bound for D-optimality with fast local search and variable-bound tightening. Math. Programming. Forthcoming. Crossref, Google Scholar
• [25] Pukelsheim F (2006) Optimal Design of Experiments (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• [26] Ravi SN, Ithapu V, Johnson S, Singh V (2016) Experimental design on a budget for sparse linear models and applications. Balcan MF, Weinberger KQ, eds. Proc. 33rd Internat. Conf. Machine Learn., Proceedings of Machine Learning Research, vol. 48 (JMLR.org), 583–592.Google Scholar
• [27] Sagnol G, Harman R (2015) Computing exact D-optimal designs by mixed integer second-order cone programming. Ann. Statist. 43(5):2198–2224.Crossref, Google Scholar
• [28] Sansone M, Fusco R, Petrillo A (2019) D-optimal design of b-values for precise intra-voxel incoherent motion imaging. Biomedical Phys. Engrg. Express 5(3):035025. Google Scholar
• [29] Singh M, Xie W (2020) Approximation algorithms for D-optimal design. Math. Oper. Res. 45(4):1512–1534.Link, Google Scholar
• [30] Spencer J (1994) Ten Lectures on the Probabilistic Method, 2nd ed. (Society for Industrial and Applied Mathematics, Philadelphia).Crossref, Google Scholar
• [31] Sviridenko M (2004) A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Let. 32(1):41–43.Crossref, Google Scholar
• [32] Tie L, Cai KY, Lin Y (2011) Rearrangement inequalities for Hermitian matrices. Linear Algebra Appl. 434(2):443–456.Crossref, Google Scholar
• [33] Vandenberghe L, Boyd S, Wu SP (1998) Determinant maximization with linear matrix inequality constraints. SIAM J. Matrix Anal. Appl. 19(2):499–533.Crossref, Google Scholar
• [34] Wang J, Xie W, Ryzhov IO, Marković N, Ou G (2025) D-optimal orienteering for post-earthquake reconnaissance planning. Oper. Res., ePub ahead of print May 16, https://doi.org/10.1287/opre.2023.0470. Google Scholar
• [35] Yaroslavtsev G, Zhou S, Avdiukhin D (2020) “Bring your own greedy”+max: Near-optimal 1/2-approximations for submodular knapsack. Chiappa S, Calandra R, eds. Proc. 23rd Internat. Conf. Artificial Intelligence Statist., Proceedings of Machine Learning Research, vol. 108 (JMLR.org), 3263–3274.Google Scholar
• [36] Zhu L, Dasgupta T, Huang Q (2014) A D-optimal design for estimation of parameters of an exponential-linear growth curve of nanostructures. Technometrics 56(4):432–442.Crossref, Google Scholar