2010/07/23 by Guillaume Sagnol, Sagnol, Guillaume · 2 citations
Engineering · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Manufacturing Process and Optimization #Mathematical Approximation and Integration #Optimization and Control (math.OC) #Optimization and Packing Problems
paper · pdf · doi:10.48550/arxiv.1007.4152
openalex publication_date 2010/07/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We study a family of combinatorial optimization problems defined by a\nparameter p\∈[0,1], which involves spectral functions applied to positive\nsemidefinite matrices, and has some application in the theory of optimal\nexperimental design. This family of problems tends to a generalization of the\nclassical maximum coverage problem as p goes to 0, and to a trivial instance\nof the knapsack problem as p goes to 1.\n In this article, we establish a matrix inequality which shows that the\nobjective function is submodular for all p\∈[0,1], from which it follows\nthat the greedy approach, which has often been used for this problem, always\ngives a design within 1-1/e of the optimum. We next study the design found by\nrounding the solution of the continuous relaxed problem, an approach which has\nbeen applied by several authors. We prove an inequality which generalizes a\nclassical result from the theory of optimal designs, and allows us to give a\nrounding procedure with an approximation factor which tends to 1 as p goes to\n1.\n