Maximizing Sub-determinants and Connections to Permanents and Inequalities on Stable Polynomials

on YouTube ↗29m

" summary

Presents a new polynomial saddle-point relaxation for maximizing det(VB^T VB) under partition matroid constraints, solved efficiently by exploiting log-concavity in log-variables, and rounded by randomized rounding per-part sampling (sample bi items from each part). Proves a 1/e^k approximation in expectation for the K=D case by reducing coefficient bounds to inequalities on stable polynomials (generalizing Gurvits’ permanent bound). The algorithm runs and achieves the claimed expectation guarantee but lacks high-probability or deterministic bounds.

AI-written summary · about

" chapters (10)

1. 0:00Problem introduction
2. 1:24Modeling via determinants
3. 3:36Constraints and motivations
4. 5:31Prior work and challenges
5. 7:39Partition constraints
6. 9:24Limitations of standard relaxations
7. 14:23Saddle point formulation
8. 20:05Randomized rounding algorithm
9. 22:45Stable polynomials and analysis
10. 25:37Conclusion and discussion