Subquadratic Algorithms for Succinct Stable Matching
Talkat Computational Complexity of Low-Polynomial Time Problems (Simons Institute workshop, 2015) · on Tuesday, 2015-12-08
summary
Provides subquadratic algorithms and matching lower bounds for succinct preference models. Claims a subquadratic one-sided D-attribute finding algorithm when women share one ranking, using geometric reduction to dynamic ray-shooting (Matoušek-style) and constant D. Gives subquadratic verification for constant D and an optimal O(dn) algorithm for d-list verification. Shows a hardness result via a reduction from Maximum Inner Product: no strongly subquadratic algorithms once D = ω(log n) (also randomized lower bounds for boolean weights when D = c log n).
AI-written summary · about
chapters (18)
- 0:00Intro
- 0:16The Stable Matching Setting
- 1:03The Stable Marriage Problem
- 1:57Gale - Shapley
- 2:51Succinct Preferences
- 3:45d-Attribute Preferences
- 4:493-attribute Preferences Example
- 5:24d-List Preferences
- 6:002-list Preferences Example
- 6:18Questions?
- 7:07Algorithmic Results
- 8:38Hardness Result
- 9:20(Boolean) Maximum Inner Product
- 9:42Reduction to Stable Matching
- 11:48d-list Stability Verification
- 14:48d-attribute Algorithms
- 16:10Finding vs. Verifying
- 17:18Future Directions