License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ISAAC.2022.46
URN: urn:nbn:de:0030-drops-173316
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17331/
Ohsaka, Naoto
On the Parameterized Intractability of Determinant Maximization
Abstract
In the Determinant Maximization problem, given an n × n positive semi-definite matrix A in ℚ^{n × n} and an integer k, we are required to find a k × k principal submatrix of 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 (2006); i.e., a f(k)n^?(1)-time algorithm is unlikely to exist for any computable function f. 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, we show that Determinant Maximization is 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 × 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√k} for some universal constant c > 0. Our hardness result is conditional on the Parameterized Inapproximability Hypothesis posed by Lokshtanov, Ramanujan, Saurab, and Zehavi (2020), which asserts that a gap version of Binary Constraint Satisfaction Problem is W[1]-hard. To complement this result, we develop an ε-additive approximation algorithm that runs in ε^{-r²}⋅r^?(r³)⋅n^?(1) time for the rank r of an input matrix, provided that the diagonal entries are bounded.
BibTeX - Entry
@InProceedings{ohsaka:LIPIcs.ISAAC.2022.46,
author = {Ohsaka, Naoto},
title = {{On the Parameterized Intractability of Determinant Maximization}},
booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)},
pages = {46:1--46:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-258-7},
ISSN = {1868-8969},
year = {2022},
volume = {248},
editor = {Bae, Sang Won and Park, Heejin},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/17331},
URN = {urn:nbn:de:0030-drops-173316},
doi = {10.4230/LIPIcs.ISAAC.2022.46},
annote = {Keywords: Determinant maximization, Parameterized complexity, Approximability}
}
|
Keywords: |
|
Determinant maximization, Parameterized complexity, Approximability |
|
Collection: |
|
33rd International Symposium on Algorithms and Computation (ISAAC 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
14.12.2022 |
