论文标题
通过Matroid交叉算法的决定性最大化
Determinant Maximization via Matroid Intersection Algorithms
论文作者
论文摘要
确定性最大化问题提供了一个一般框架，该框架模拟了在统计范围内产生的问题\ cite {pukelsheim2006optimal}，convex几何\ cite {khachiyan1996}，公平分配\ line分配\ line break \ cite \ cite {anarii2016nash} anar}光谱图理论\ cite {nikolov2019proportional}，网络设计和随机过程\ cite {kulesza2012determinantal}。在确定性最大化问题的情况下，我们将为我们提供了一个向量的集合，$ u = \ {v_1，\ ldots，v_n \} \ subset \ rr^d $，一个目标是选择一个子集$ s \ subseteq u $ $ subseteq u $ sum__ $ sum__ sum__} sum______i v_i^\ top $。通常，挑选向量的集合$ s $必须满足其他组合约束，例如基数约束$ \ left（| s | \ leq k \ right）$或matroid约束（$ s $是向量上定义的矩阵的基础）。 在本文中，我们给出了一个多项式确定性算法，该算法返回$ r^{o（r）} $ - 对于任何等级$ r \ r \ leq d $的矩形的近似值。 This improves previous results that give $e^{O(r^2)}$-approximation algorithms relying on $e^{O(r)}$-approximate \emph{estimation} algorithms \cite{NikolovS16,anari2017generalization,AnariGV18,madan2020maximizing} for any $r\leq d$.所有先前的结果都使用凸松弛及其与稳定多项式的关系和强烈的对数符号多项式。相比之下，我们的算法建立在用于矩阵相交的组合算法的基础上，通过在矩阵定义的\ emph {exchange graph}中找到\ emph {交替的负循环}，可以迭代地改善任何解决方案。虽然$ \ det（。）$函数不是线性的，但我们表明，在每次迭代时进行适当的线性近似足以给出改进的近似算法。
Determinant maximization problem gives a general framework that models problems arising in as diverse fields as statistics \cite{pukelsheim2006optimal}, convex geometry \cite{Khachiyan1996}, fair allocations\linebreak \cite{anari2016nash}, combinatorics \cite{AnariGV18}, spectral graph theory \cite{nikolov2019proportional}, network design, and random processes \cite{kulesza2012determinantal}. In an instance of a determinant maximization problem, we are given a collection of vectors $U=\{v_1,\ldots, v_n\} \subset \RR^d$, and a goal is to pick a subset $S\subseteq U$ of given vectors to maximize the determinant of the matrix $\sum_{i\in S} v_i v_i^\top $. Often, the set $S$ of picked vectors must satisfy additional combinatorial constraints such as cardinality constraint $\left(|S|\leq k\right)$ or matroid constraint ($S$ is a basis of a matroid defined on the vectors). In this paper, we give a polynomial-time deterministic algorithm that returns a $r^{O(r)}$-approximation for any matroid of rank $r\leq d$. This improves previous results that give $e^{O(r^2)}$-approximation algorithms relying on $e^{O(r)}$-approximate \emph{estimation} algorithms \cite{NikolovS16,anari2017generalization,AnariGV18,madan2020maximizing} for any $r\leq d$. All previous results use convex relaxations and their relationship to stable polynomials and strongly log-concave polynomials. In contrast, our algorithm builds on combinatorial algorithms for matroid intersection, which iteratively improve any solution by finding an \emph{alternating negative cycle} in the \emph{exchange graph} defined by the matroids. While the $\det(.)$ function is not linear, we show that taking appropriate linear approximations at each iteration suffice to give the improved approximation algorithm.
