论文标题
Plücker关系与应用于亚次级最大化的应用的扩展
An Extension of Plücker Relations with Applications to Subdeterminant Maximization
论文作者
论文摘要
给定一个矩阵$ a $和$ k \ geq 0 $，我们研究了查找$ k \ times k $ subsatrix of $ a $的问题，具有绝对值的最大决定因素。该问题是由[LSV86]在遗传差异上计算基于决定因素的下限的问题，后来证明这是一个近似的上限[MAT13]。 $ k $与$ a $的尺寸之一相吻合的特殊情况已得到广泛的研究。 [Nik15]给出了$ 2^{o（k）} $ - 该特殊情况的近似算法，与已知的下限匹配；他还提出了一个开放问题，即为一般情况设计近似算法的问题。 我们通过给出第一个有效的近似算法的$ k \ times k $ subsederminant最大化，并以仅取决于$ k $的近似值来回答这个问题。我们的算法通过执行简单的本地搜索来找到$ k^{o（k）} $ - 近似解决方案。我们的主要技术贡献，实现了近似比的分析，是格拉马尼亚人的plücker关系的扩展，这可能具有独立的利益； plücker关系是二次多项式方程，涉及$ k $ subsedermants a $ k \ times n $矩阵的集合。我们发现，这些关系的扩展为$ k \ times k $ subsederments $ m \ times n $矩阵。
Given a matrix $A$ and $k\geq 0$, we study the problem of finding the $k\times k$ submatrix of $A$ with the maximum determinant in absolute value. This problem is motivated by the question of computing the determinant-based lower bound of [LSV86] on hereditary discrepancy, which was later shown to be an approximate upper bound as well [Mat13]. The special case where $k$ coincides with one of the dimensions of $A$ has been extensively studied. [Nik15] gave a $2^{O(k)}$-approximation algorithm for this special case, matching known lower bounds; he also raised as an open problem the question of designing approximation algorithms for the general case. We make progress towards answering this question by giving the first efficient approximation algorithm for general $k\times k$ subdeterminant maximization with an approximation ratio that depends only on $k$. Our algorithm finds a $k^{O(k)}$-approximate solution by performing a simple local search. Our main technical contribution, enabling the analysis of the approximation ratio, is an extension of Plücker relations for the Grassmannian, which may be of independent interest; Plücker relations are quadratic polynomial equations involving the set of $k\times k$ subdeterminants of a $k\times n$ matrix. We find an extension of these relations to $k\times k$ subdeterminants of general $m\times n$ matrices.
