×

Submodularity and randomized rounding techniques for optimal experimental design. (English) Zbl 1237.93057

Haouari, M. (ed.) et al., ISCO 2010. International symposium on combinatorial optimization. Papers based on the presentations at the symposium, Hammamet, Tunesia, March 24–26, 2010. Amsterdam: Elsevier. Electronic Notes in Discrete Mathematics 36, 679-686 (2010).
Summary: We review recent results obtained by the authors on the approximability of a family of combinatorial problems arising in optimal experimental design. We first recall a result based on submodularity, which states that the greedy approach always gives a design within \(1 - 1/e\) of the optimal solution. Then, we present a new result on the design found by rounding the solution of the continuous relaxed problem, an approach which has been applied by several authors: When the goal is to select \(n\) out of \(s\) experiments, the \(D\)-optimal design may be rounded to a design for which the dimension of the observable subspace is within of the optimum.
For the entire collection see [Zbl 1236.90011].

MSC:

93B51 Design techniques (robust design, computer-aided design, etc.)
65Y99 Computer aspects of numerical algorithms

Software:

NetQuest
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ageev, A. A.; Sviridenko, M. I., Pipage rounding: a new method of constructing algorithms with proven performance guarantee, Journal of Combinatorial Optimization, 8 (2004) · Zbl 1084.90029
[2] Atwood, C. L., Sequences converging to D-optimal designs of experiments, Annal of statistics, 1, 342-352 (1973) · Zbl 0263.62047
[3] Branderhorst, M.; Walmsley, I.; Kosut, R.; Rabitz, H., Optimal experiment design for quantum state tomography of a molecular vibrational mode, Journal of Physics B: Atomic Molecular and Optical Physics, 41 (2008), 074004
[4] G. Calinescu, C. Chekuri, M. Pál, and J. Vondrák. Maximizing a submodular set function subject to a matroid constraint. In Proceedings of the 12th international conference on Integer Programming and Combinatorial Optimization, IPCO; G. Calinescu, C. Chekuri, M. Pál, and J. Vondrák. Maximizing a submodular set function subject to a matroid constraint. In Proceedings of the 12th international conference on Integer Programming and Combinatorial Optimization, IPCO · Zbl 1136.90449
[5] Dette, H.; Pepelyshev, A.; Zhigljavsky, A., Improving updating rules in multiplicative algorithms for computing D-optimal designs, Computational Statistics & Data Analysis, 53, 2, 312-320 (2008) · Zbl 1231.62141
[6] Fedorov, V. V., Theory of optimal experiments (1972), Academic Press: Academic Press New York, Translated and edited by W. J. Studden and E. M. Klimko
[7] Kiefer, J., Optimal design: Variation in structure and performance under change of criterion, Biometrika, 62, 2, 277-288 (1975) · Zbl 0321.62086
[8] A. Kulik, H. Shachnai, and T. Tamir. Maximizing submodular set functions subject to multiple linear constraints. In SODA ’09: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms; A. Kulik, H. Shachnai, and T. Tamir. Maximizing submodular set functions subject to multiple linear constraints. In SODA ’09: Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms · Zbl 1423.90230
[9] Nemhauser, G. L.; Wolsey, L. A.; Fisher, M. L., An analysis of approximations for maximizing submodular set functions, Mathematical Programming, 14, 265-294 (1978) · Zbl 0374.90045
[10] Pukelsheim, F., On linear regression designs which maximize information, Journal of statistical planning and inferrence, 4, 339-364 (1980) · Zbl 0472.62079
[11] Pukelsheim, F., Optimal Design of Experiments (1993), Wiley · Zbl 0834.62068
[12] G. Sagnol. Polynomial-time approximability results for combinatorial problems arising in optimal experimental design. Draft; G. Sagnol. Polynomial-time approximability results for combinatorial problems arising in optimal experimental design. Draft
[13] G. Sagnol, M. Bouhtou, and S. Gaubert. Optimization of network traffic measurement: a semidefinite programming approach. In Proceedings of the International Conference on Engineering Optimization (ENGOPT); G. Sagnol, M. Bouhtou, and S. Gaubert. Optimization of network traffic measurement: a semidefinite programming approach. In Proceedings of the International Conference on Engineering Optimization (ENGOPT)
[14] H.H. Song, L. Qiu, and Y. Zhang. Netquest: A flexible framework for largescale network measurement. In ACM SIGMETRICS’06; H.H. Song, L. Qiu, and Y. Zhang. Netquest: A flexible framework for largescale network measurement. In ACM SIGMETRICS’06
[15] Uciński, D.; Patan, M., D-optimal design of a monitoring network for parameter estimation of distributed systems, Journal of Global Optimization, 39, 2, 291-322 (2007) · Zbl 1180.90173
[16] Yu, Y., Monotonic convergence of a general algorithm for computing optimal designs (2009)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.