Anari, Nima ;
Vuong, ThuyDuong
An Extension of Plücker Relations with Applications to Subdeterminant Maximization
Abstract
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 determinantbased 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.
BibTeX  Entry
@InProceedings{anari_et_al:LIPIcs:2020:12659,
author = {Nima Anari and ThuyDuong Vuong},
title = {{An Extension of Pl{\"u}cker Relations with Applications to Subdeterminant Maximization}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
pages = {56:156:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771641},
ISSN = {18688969},
year = {2020},
volume = {176},
editor = {Jaros{\l}aw Byrka and Raghu Meka},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12659},
URN = {urn:nbn:de:0030drops126596},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2020.56},
annote = {Keywords: Pl{\"u}cker relations, determinant maximization, local search, exchange property, discrete concavity, discrepancy}
}
11.08.2020
Keywords: 

Plücker relations, determinant maximization, local search, exchange property, discrete concavity, discrepancy 
Seminar: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Issue date: 

2020 
Date of publication: 

11.08.2020 