Low-Sensitivity Matching via Sampling from Gibbs Distributions
Abstract
In this work, we study the maximum matching problem from the perspective of sensitivity. The sensitivity of an algorithm \(A\) on a graph \(G\) is defined as the maximum Wasserstein distance between the output distributions of \(A\) on \(G\) and on \(G - e\), where \(G - e\) is the graph obtained by deleting an edge \(e\) from \(G\). The maximum is taken over all edges \(e\), and the underlying metric for the Wasserstein distance is the Hamming distance.
Fields of Study & Subjects
Markov Chains and Monte Carlo Methods
Random Matrices and Applications
Limits and Structures in Graph Theory
Publication details
- Journal / source
- Society for Industrial and Applied Mathematics eBooks
- Pages
- 120–149
- Publication date
- 1 January 2026
- Language
- EN