Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration

DOI10.1137/19M1309523zbMath1506.68181arXiv1707.02757OpenAlexW3112877925MaRDI QIDQ3387758

Nisheeth K. Vishnoi, Damian Straszak, Javad B. Ebrahimi

Publication date: 13 January 2021

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1707.02757

zbMATH Keywords

matroidsapproximation algorithmsanti-concentrationsubdeterminant maximization

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Analysis of algorithms (68W40) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Cites Work

• Unnamed Item
• Unnamed Item
• Random symmetric matrices are almost surely nonsingular.
• On selecting a maximum volume sub-matrix of a matrix and related problems
• On the complexity of approximating extremal determinants in matrices
• Determinantal probability measures
• Largest \(j\)-simplices in \(n\)-polytopes
• Algebraic Algorithms for Linear Matroid Parity Problems
• A Robust Khintchine Inequality, and Algorithms for Computing Optimal Constants in Fourier Analysis and High-Dimensional Geometry
• Determinantal Point Processes for Machine Learning
• Hyperbolic polynomials approach to Van der Waerden/Schrijver-Valiant like conjectures
• Randomized Rounding for the Largest Simplex Problem
• Real Advantage
• Algebraic Algorithms for Matching and Matroid Problems
• Singular spaces of matrices and their application in combinatorics
• Real stable polynomials and matroids: optimization and counting
• A generalization of permanent inequalities and applications in counting and optimization
• Linear matroid intersection is in quasi-NC
• On the Complexity of Constrained Determinantal Point Processes
• Analysis of Boolean Functions
• Maximizing determinants under partition constraints
• On largest volume simplices and sub-determinants
• Distributional and \(L^q\) norm inequalities for polynomials over convex bodies in \(\mathbb{R}^n\)

This page was built for publication: Subdeterminant Maximization via Nonconvex Relaxations and Anti-Concentration