论文标题
在矩阵约束下最大化决定因素
Maximizing Determinants under Matroid Constraints
论文作者
论文摘要
给定vectors $ v_1，\ dots，v_n \ in \ mathbb {r}^d $和a matroid $ m =（[n]，i）$，我们研究了找到$ m $ $ s $ s $ s $ s $ s $ s $ m $的问题（\ sum_ \ sum_ {\ sum_ {i \ in s} v_i v_i v_i v_i v_i^\ top top top top top top）这个问题出现在各种各样的领域，例如实验设计，商品的公平分配，网络设计和机器学习。当前的最佳结果包括$ e^{2k} $ - 对等级$ k $的任何配件的估计和$（1+ε）^d $ - approximation，用于等级$ k \ ge d+\ d+\ fracdε$的均匀矩阵，等级$ k \ ge d $表示最佳设置所需的最佳尺寸。我们的主要结果是一种新的近似算法，并具有近似保证，仅取决于向量的尺寸$ d $，而不取决于输出集的尺寸$ k $。特别是，我们显示了一个$（o（d））^{d} $ - 估计和$（o（d））^{d^3} $ - 对于任何Matroid来说，近似值，在$ k \ gg d $时对先前工作进行了重大改进。 我们的结果依赖于存在稀疏支持的问题的最佳解决方案。特别是，解决方案的变量不超过$ o（d^2）$变量具有分数值。稀疏性结果依赖于凸程序的一阶最优条件与矩形理论之间的相互作用。我们认为，引入的技术表明凸面程序的最佳解决方案的稀疏性将引起独立的兴趣。我们还提供了一种随机算法，该算法将稀疏的分数解决方案四舍五入为原始问题的可行积分解决方案。为了显示近似保证，我们利用了最新的作品在强烈的对数符号多项式上，并显示了研究该问题的不同凸面程序之间的新关系。最后，我们使用估计算法和稀疏结果来提供有效的确定性近似算法，并具有仅取决于尺寸$ d $的近似保证。
Given vectors $v_1,\dots,v_n\in\mathbb{R}^d$ and a matroid $M=([n],I)$, we study the problem of finding a basis $S$ of $M$ such that $\det(\sum_{i \in S}v_i v_i^\top)$ is maximized. This problem appears in a diverse set of areas such as experimental design, fair allocation of goods, network design, and machine learning. The current best results include an $e^{2k}$-estimation for any matroid of rank $k$ and a $(1+ε)^d$-approximation for a uniform matroid of rank $k\ge d+\frac dε$, where the rank $k\ge d$ denotes the desired size of the optimal set. Our main result is a new approximation algorithm with an approximation guarantee that depends only on the dimension $d$ of the vectors and not on the size $k$ of the output set. In particular, we show an $(O(d))^{d}$-estimation and an $(O(d))^{d^3}$-approximation for any matroid, giving a significant improvement over prior work when $k\gg d$. Our result relies on the existence of an optimal solution to a convex programming relaxation for the problem which has sparse support; in particular, no more than $O(d^2)$ variables of the solution have fractional values. The sparsity results rely on the interplay between the first-order optimality conditions for the convex program and matroid theory. We believe that the techniques introduced to show sparsity of optimal solutions to convex programs will be of independent interest. We also give a randomized algorithm that rounds a sparse fractional solution to a feasible integral solution to the original problem. To show the approximation guarantee, we utilize recent works on strongly log-concave polynomials and show new relationships between different convex programs studied for the problem. Finally, we use the estimation algorithm and sparsity results to give an efficient deterministic approximation algorithm with an approximation guarantee that depends solely on the dimension $d$.
