4 papers · 1 filter
Low-Sensitivity Matching via Sampling from Gibbs Distributions
Yuichi Yoshida, Zihan Zhang
In this work, we study the maximum matching problem from the perspective of sensitivity. The sensitivity of an algorithm on a graph is defined as the maximum Wasserstein di…
Pointwise Lipschitz Continuous Graph Algorithms
Quanquan C. Liu, Grigoris Velegkas, Yuichi Yoshida +1
In many real-world applications, it is undesirable to drastically change the problem solution after a small perturbation in the input, as unstable outputs can lead to costly transa…
-Approximation Algorithms for Bipartiteness Ratio
Tasuku Soma, Mingquan Ye, Yuichi Yoshida
We propose an -approximation algorithm for the bipartiteness ratio of undirected graphs introduced by Trevisan (SIAM Journal on Computing, vol. 41, no. 6, 2012), where $…
Sensitivity Lower Bounds for Approximaiton Algorithms
Noah Fleming, Yuichi Yoshida
Sensitivity measures how much the output of an algorithm changes, in terms of Hamming distance, when part of the input is modified. While approximation algorithms with low sensitiv…