Refine
Year of publication
Document Type
- ZIB-Report (26)
- Article (13)
- In Proceedings (13)
- Other (1)
Is part of the Bibliography
- no (53)
Keywords
- Optimal Experimental Design (3)
- SDP (3)
- Flows in graphs (2)
- Game Theory (2)
- Hilbert's projective metric (2)
- Integer Programming (2)
- Mixed Integer Programming (2)
- SOCP (2)
- Semidefinite Programming (2)
- Stackelberg Equilibrium (2)
- Vehicle Routing Problem (2)
- lognormal duration (2)
- robust optimization (2)
- Approximation Algorithms (1)
- Approximation Hierarchies (1)
- Approximation hierarchies (1)
- Controls in transportation networks (1)
- Copositive Programming (1)
- Copositive programming (1)
- Cutting plane algorithm (1)
- D-optimality (1)
- Design efficiency (1)
- Duty Roster Planning (1)
- Duty Rostering (1)
- Equivalence theorem (1)
- Exact Designs (1)
- Extensible Bin Packing (1)
- Gaussian Process (1)
- Kalman Filter (1)
- Kiefer's p-criterion (1)
- Low-rank solutions (1)
- Maximum Coverage (1)
- Model-based optimal design (1)
- Multiresponse experiments (1)
- Network measurements (1)
- Nonlinear programming (1)
- Operations Research (1)
- Optimal Design (1)
- Optimal Design of Experiments (1)
- Optimal design of computer experiments (1)
- Optimal design of experiments (1)
- Polymatrix game (1)
- Polynomial Time Approximability (1)
- Price of Anarchy (1)
- Robust minmax designs (1)
- SOCP Representability (1)
- Second Order Cone Programming (1)
- Security Games (1)
- Semidefinite Packing Problem (1)
- Semidefinite programming (1)
- Sparse kernels (1)
- Stackelberg game (1)
- Stochastic Scheduling (1)
- Toll Enforcement (1)
- activity network (1)
- bicriteria optimization (1)
- branch and bound (1)
- crew rostering (1)
- integer programming (1)
- lognormal distribution (1)
- mathematical programming (1)
- matrix geometric mean (1)
- network interdiction (1)
- nuisance trend (1)
- optimal design of experiments (1)
- optimal experimental designs (1)
- python (1)
- rank 1-solution (1)
- scheduling (1)
- semidefinite representability (1)
- vehicle routing (1)
Institute
- Mathematical Optimization (52)
- Mathematics of Transportation and Logistics (28)
- Mathematics of Health Care (16)
- Network Optimization (2)
- Visual Data Analysis (2)
- Visual and Data-centric Computing (2)
- Computational Medicine (1)
- Numerical Mathematics (1)
- Visual Data Analysis in Science and Engineering (1)
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$.