2 papers
cs.DS2026
On the Efficiency of Sinkhorn-Knopp for Entropically Regularized Optimal Transport
Kun He
The Sinkhorn--Knopp (SK) algorithm is a cornerstone method for matrix scaling and entropically regularized optimal transport (EOT). Despite its empirical efficiency, existing theor…
cs.DS2025
Sampling permutations satisfying constraints within the lopsided local lemma regime
Kun He, Guoliang Qiu, Xiaoming Sun
Sampling a random permutation with restricted positions, or equivalently approximating the permanent of a 0-1 matrix, is a fundamental problem in computer science, with several not…