Near-Linear Time Generalized Sinkhorn Algorithms for Bounded Genus Graphs

Krzysztof Choromanski, Derek Long, Ananya Parashar +1

We present GenusSink, a new class of approximate generalized Sinkhorn algorithms with shortest-path-distance costs for bounded genus (e.g. planar) graphs, providing near-linear tim…