کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
421193 684158 2013 19 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Approximation of a maximum-submodular-coverage problem involving spectral functions, with application to experimental designs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Approximation of a maximum-submodular-coverage problem involving spectral functions, with application to experimental designs
چکیده انگلیسی

We study a family of combinatorial optimization problems defined by a parameter p∈[0,1]p∈[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 pp goes to 0, and to a trivial instance of the knapsack problem as pp goes to 1.In this article, we establish a matrix inequality which shows that the objective function is submodular for all p∈[0,1]p∈[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/e1−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 pp goes to 1.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 161, Issues 1–2, January 2013, Pages 258–276
نویسندگان
,