A Fast Algorithm for Computing the Maximum Weight Base in a Linear Matroid

on YouTube ↗26m

" summary

Presents an algorithm that outputs the greedy maximum-weight base of a linear matroid in time roughly the number of nonzeros of the input matrix plus r^{ω} plus a mild n^{1+o(1)} overhead, where r is the rank. It achieves this by using rank-preserving linear sketches to compress intervals of columns, then a divide-and-conquer with projections that contracts selected columns and recurses, with O(log n) filtering rounds; works as a first concrete speedup when n ≫ r.

AI-written summary · about

" chapters (13)

1. 0:00Introduction
2. 0:36Background
3. 3:23Definition of Major
4. 4:59Spanning Tree
5. 5:48Linear vectors
6. 7:08Maximum weight spanning trees
7. 7:58Computing the maximum weight base
8. 9:17Special cases
9. 13:02Method
10. 13:43Rank Sketch
11. 15:30Divine Contour
12. 17:57Running Time
13. 22:20Problem Solving

" related talks

• 29mSampling Algorithms for Combinatorial Pure ExplorationAnupam Gupta · Optimization, Statistics and Uncertainty
• 47mSuccinct Representations and Efficient Algorithms Based on Linear ProgrammingSudipto Guha · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 42mDimensionality Reduction Via Sparse MatricesJelani Nelson · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)
• 51mNearly Linear Time Algorithms for Solving Inverse Symmetric M-MatricesAaron Sidford · Sublinear Algorithms and Nearest-Neighbor Search
• 30mOn Approximation Guarantees for Greedy Low Rank OptimizationSahand Negahban · Optimization, Statistics and Uncertainty
• 01h 31mPast, Present and Future of Randomized Numerical Linear Algebra IIMichael Mahoney, Petros Drineas · Big Data Boot Camp 2013
• 42mLearning What Works Best WhenSwati Gupta · Real-Time Decision Making 2018
• 36mThe Rank of Sparse Random MatricesJane Gao · Computational Phase Transitions (Simons Institute, 2020)