1495
eng
258
276
1--2
151
reportzib
0
2012-03-27
2012-03-27
--
Approximation of a Maximum-Submodular-Coverage problem involving spectral functions, with application to Experimental Design
We study a family of combinatorial optimization problems
defined by a parameter $p\in[0,1]$, which involves spectral
functions applied to positive semidefinite matrices, and has
some application in the theory of optimal experimental design.
This family of problems tends to a generalization of the classical
maximum coverage problem as $p$ goes to $0$, and to a trivial instance
of the knapsack problem as $p$ goes to $1$.
In this article, we establish a matrix inequality which shows that the objective function is submodular for all $p\in[0,1]$, from which it follows
that the greedy approach, which has often been used for this problem, always gives a design within $1-1/e$ of the optimum.
We next study the design found by rounding the solution of the continuous relaxed problem, an approach which has been applied by several authors.
We prove an inequality which generalizes a classical result from the theory
of optimal designs, and allows us to give a rounding procedure with an approximation
factor which tends to $1$ as $p$ goes to $1$.
1438-0064
urn:nbn:de:0297-zib-14956
10.1016/j.dam.2012.07.016
Appeared in: Discrete Applied Mathematics
Guillaume Sagnol
Guillaume Sagnol
ZIB-Report
11-53
eng
uncontrolled
Maximum Coverage
eng
uncontrolled
Optimal Experimental Design
eng
uncontrolled
Polynomial Time Approximability
eng
uncontrolled
Kiefer's p-criterion
OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING
Mathematical Optimization
Sagnol, Guillaume
https://opus4.kobv.de/opus4-zib/files/1495/submodular_zib.pdf