Maximizing Determinants under Matroid Constraints
Maximizing Determinants under Matroid Constraints
复制标题
DOI：
10.1109/focs46700.2020.00059
复制
发表时间：
2020-04
期刊：
影响因子：
--
通讯作者：
V. Madan;Aleksandar Nikolov;Mohit Singh;U. Tantipongpipat
中科院分区：
文献类型：
--
作者：
V. Madan;Aleksandar Nikolov;Mohit Singh;U. Tantipongpipat
给定一组矢量$ \ mathbf {v} _ {1}，\ ldots，\ mathbf {v} _ {n} \ in \ mathbb {r}^d}^{d} $ （[n]，\ Mathcal {i}）$，我们研究找到$ \ MATHCAL {m} $的基础$ s $的问题，以便$ \ det（\ sum \ nolimits_ {i \ {v} _ {i} \ Mathbf {v} _ {i}^{\ top}）$最大化。这个问题出现在各种各样的领域，例如实验设计，商品的公平分配，网络设计和机器学习。当前最佳结果包括任何等级$ k $ [8]和$（1+ \ epsilon）^{d} $的$ e^{2k} $ - 均匀的均匀矩阵的近似值（$ k $ [8]） \ geq d+\ frac {d} {\ epsilon} $ [30]，其中等级$ k \ geq d $表示最佳集合所需的大小。我们的主要结果是用于一般问题的新近似算法，其近似保证仅取决于向量的尺寸$ d $，而不是输出集的尺寸$ k $。特别是，我们显示$（o（d））^{d} $ - 估算和$（o（d））^{d^{3}} $ - 任何矩阵的近似值$ k \ gg d $时工作。我们的结果依赖于表明，对于稀疏支持的问题，存在一个最佳解决方案；特别是，解决方案的变量不超过$ o（d^{2}）$变量具有分数值。稀疏性结果依赖于凸程序的一阶最优条件与Matroid理论之间的相互作用。我们认为，引入的技术表明凸面程序的最佳解决方案的稀疏性将引起独立的兴趣。我们还提供了一种新的随机圆形算法，该算法至关重要地利用了凸面程序的解决方案的稀疏性。为了显示近似保证，我们利用了最新的作品在强烈的对数conconcave多项式[8]，[4]上，并显示了针对该问题的不同凸程序[33] [33] [6]之间的新关系。最后，我们展示了如何使用估计算法来提供有效的确定性近似算法。再次，该算法至关重要地依赖于分数解的稀疏性来确保近似因子仅取决于尺寸$ d $。
Given a set of vectors $\mathbf{v}_{1}, \ldots, \mathbf{v}_{n}\in \mathbb{R}^{d}$ and a matroid $\mathcal{M}=([n],\mathcal{I})$, we study the problem of finding a basis $S$ of $\mathcal{M}$ such that $\det(\sum\nolimits_{i\in S}\mathbf{v}_{i}\mathbf{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$ [8] and a $(1+\epsilon)^{d}$-approximation for a uniform matroid of rank $k \geq d+\frac{d}{\epsilon}$ [30], where the rank $k\geq d$ denotes the desired size of the optimal set. Our main result is a new approximation algorithm for the general problem 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 showing that there exists 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 new randomized rounding algorithm that crucially exploits the sparsity of solutions to the convex program. To show the approximation guarantee, we utilize recent works on strongly log-concave polynomials [8], [4] and show new relationships between different convex programs [33], [6] studied for the problem. Finally, we show how to use the estimation algorithm to give an efficient deterministic approximation algorithm. Once again, the algorithm crucially relies on sparsity of the fractional solution to guarantee that the approximation factor depends solely on the dimension $d$.