文章基本信息

标题：An Extension of PlÃ¼cker Relations with Applications to Subdeterminant Maximization
本地全文：下载
作者：Nima Anari ; Thuy-Duong Vuong
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：176
页码：56:1-56:16
DOI：10.4230/LIPIcs.APPROX/RANDOM.2020.56
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Given a matrix A and k â¥ 0, we study the problem of finding the k Ã- 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 cite{LSV86} on hereditary discrepancy, which was later shown to be an approximate upper bound as well [MatouÅ¡ek, 2013]. The special case where k coincides with one of the dimensions of A has been extensively studied. Nikolov 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Ã- 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Ã- k subdeterminants of a kÃ- n matrix. We find an extension of these relations to kÃ- k subdeterminants of general mÃ- n matrices.
关键词：PlÃ¼cker relations; determinant maximization; local search; exchange property; discrete concavity; discrepancy