NSF PAR Search | NSF Public Access Repository

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

Scalable Algorithm for Finding Balanced Subgraphs with Tolerance in Signed Networks

https://doi.org/10.1145/3637528.3671674

Chen, Jingbang; Mang, Qiuyang; Zhou, Hangrui; Peng, Richard; Gao, Yu; Ma, Chenhao (August 2024, KDD 2024)

Full Text Available
Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, s-t Shortest Path, and Minimum-Cost Flow

https://doi.org/10.1145/3618260.3649745

Chen, Li; Kyng, Rasmus; Liu, Yang P; Meierhans, Simon; Probst_Gutenberg, Maximilian (June 2024, ACM)

Full Text Available
Incremental Approximate Maximum Flow on Undirected Graphs in Subpolynomial Update Time

van_den_Brand, Jan; Chen, Li; Kyng, Rasmus; Liu, Yang P; Peng, Richard; Gutenberg, Maximilian Probst; Sachdeva, Sushant; Sidford, Aaron (January 2024, SODA 2024)

Full Text Available
Exponential Convergence of Sinkhorn Under Regularization Scheduling

Jingbang Chen, Li Chen (January 2023, SIAM Conference on Applied and Computational Discrete Algorithms (ACDA23))
Jonathan Berry, David Shmoys (Ed.)
n 2013, Cuturi [9] introduced the SINKHORN algorithm for matrix scaling as a method to compute solutions to regularized optimal transport problems. In this paper, aiming at a better convergence rate for a high accuracy solution, we work on understanding the SINKHORN algorithm under regularization scheduling, and thus modify it with a mechanism that adaptively doubles the regularization parameter η periodically. We prove that such modified version of SINKHORN has an exponential convergence rate as iteration complexity depending on log(l/ɛ) instead of ɛ-o(1) from previous analyses [1, 9] in the optimal transport problems with integral supply and demand. Furthermore, with cost and capacity scaling procedures, the general optimal transport problem can be solved with a logarithmic dependence on 1/ɛ as well.
more » « less
Full Text Available

Search for: All records