Subdeterminant Maximization via Nonconvex Relaxations and Anti-concentration
summary
Presents randomized algorithms that actually output sets for constrained subdeterminant maximization over regular matroids and partition matroids, using a nonconvex multilinear relaxation plus simple rounding. For regular matroids the algorithm returns a set within about 2^{-m} of optimum (high probability); for partition matroids with bounded part size the guarantee becomes roughly e^{O(r)}. Proofs replace real-stability tools with a new anti-concentration inequality and sampling-plus-rounding that provably works.
AI-written summary · about