论文标题
关于决定性最大化的参数性无关性
On the Parameterized Intractability of Determinant Maximization
论文作者
论文摘要
在确定性的最大化问题中，给定一个$ n $ n $阳性半定位矩阵$ \ bf {a} $中的$ \ mathbb {q}^{q}^{n \ times n} $和一个整数$ k $，我们需要找到$ k \ times k \ times k \ times k \ times k $ k $ principal subbsatrix of $ \ bf \ bf = a} a}。众所周知，这个问题是NP坚硬的，并且相对于Koutis的$ k $而被证明是w [1]。但是，在限制情况下，仍然有空间可以探索其参数化的复杂性，以克服一般的参数化棘手性。在这项研究中，即使输入矩阵极为稀疏或级别，我们排除了决定性最大化的固定参数障碍性，或者可以接受近似解决方案。我们首先证明，即使输入矩阵是箭头矩阵，确定性最大化是NP-HARD和W [1] -HARD。即，非零条目形成的基础图是恒星，这意味着结构稀疏性无济于事。相比之下，已知决定性最大化是在三角形矩阵上的多项式时间内可溶的。此后，我们演示了有关输入矩阵的等级$ r $的w [1] - hard。我们的结果比Koutis的结果更强，因为每当$ k> r $ $ $时，任何$ k \ times k $ principal submatrix都是单数的。我们最终提供了证据表明，对于某些通用常数$ c> 0 $，$ k $在$ 2^{ - c \ sqrt {k}} $中近似于$ k $参数的近似确定性最大化。我们的硬度结果是基于Lokshtanov，Ramanujan，Saurab和Zehavi提出的参数化的不Ximimibility假设的条件，该假设断言二进制约束满意度问题的间隙版本是W [1] -hard。为了补充这一结果，我们开发了一种$ \ varepsilon $ - addive近似算法，该算法以$ \ varepsilon^{ - r^2} \ cdot r^{o（r^3）} \ cdot n^{o（r^3）} \ cdot n^{o（1）} $ r $ r $ r $ r $ diag are diAged at diAgg而均为diagn and and diagon。
In the Determinant Maximization problem, given an $n\times n$ positive semi-definite matrix $\bf{A}$ in $\mathbb{Q}^{n\times n}$ and an integer $k$, we are required to find a $k\times k$ principal submatrix of $\bf{A}$ having the maximum determinant. This problem is known to be NP-hard and further proven to be W[1]-hard with respect to $k$ by Koutis. However, there is still room to explore its parameterized complexity in the restricted case, in the hope of overcoming the general-case parameterized intractability. In this study, we rule out the fixed-parameter tractability of Determinant Maximization even if an input matrix is extremely sparse or low rank, or an approximate solution is acceptable. We first prove that Determinant Maximization is NP-hard and W[1]-hard even if an input matrix is an arrowhead matrix; i.e., the underlying graph formed by nonzero entries is a star, implying that the structural sparsity is not helpful. By contrast, Determinant Maximization is known to be solvable in polynomial time on tridiagonal matrices. Thereafter, we demonstrate the W[1]-hardness with respect to the rank $r$ of an input matrix. Our result is stronger than Koutis' result in the sense that any $k\times k$ principal submatrix is singular whenever $k>r$. We finally give evidence that it is W[1]-hard to approximate Determinant Maximization parameterized by $k$ within a factor of $2^{-c\sqrt{k}}$ for some universal constant $c>0$. Our hardness result is conditional on the Parameterized Inapproximability Hypothesis posed by Lokshtanov, Ramanujan, Saurab, and Zehavi, which asserts that a gap version of Binary Constraint Satisfaction Problem is W[1]-hard. To complement this result, we develop an $\varepsilon$-additive approximation algorithm that runs in $\varepsilon^{-r^2}\cdot r^{O(r^3)}\cdot n^{O(1)}$ time for the rank $r$ of an input matrix, provided that the diagonal entries are bounded.
