A framework for dynamic matching in weighted graphs
Aaron Bernstein, Aditi Dudeja, Zachary Langley
Abstract
We introduce a new framework for computing approximate maximum weight matchings. Our primary focus is on the fully dynamic setting, where there is a large gap between the guarantees of the best known algorithms for computing weighted and unweighted matchings. Indeed, almost all current weighted matching algorithms that reduce to the unweighted problem lose a factor of two in the approximation ratio. In contrast, in other sublinear models such as the distributed and streaming models, recent work has largely closed this weighted/unweighted gap.
Topics & Concepts
Sublinear functionMatching (statistics)Computer scienceContrast (vision)Approximation algorithmFocus (optics)Current (fluid)AlgorithmTheoretical computer scienceMathematical optimizationMathematicsCombinatoricsArtificial intelligenceElectrical engineeringEngineeringStatisticsPhysicsOpticsOptimization and Search ProblemsComplexity and Algorithms in GraphsCaching and Content Delivery