4 papers
On the Communication Complexity of Maximum Matching and Negative-Weight Shortest Paths
Yu Cheng, Tianle Jiang, Pachara Sawettamalya +1
We revisit several fundamental graph problems in the deterministic two-party communication model. Our main contributions include: (1) a new -bit protocol fo…
On the Cost of Non-Adaptivity in Matroid Prophet Inequalities
Tianle Jiang
Matroid prophet inequalities admit an optimal 2-competitive algorithm, which relies on adaptively updating thresholds based on previous outcomes. Motivated by applications to poste…
Simple KNN-Based Outlier Detection Achieves Robust Clustering
Tianle Jiang, Yufa Zhou
Being robust to the presence of outliers is crucial for applying clustering algorithms in practice. In the $\textit{robust $k$-Means}$ problem (i.e., -Means with outliers), the…
Edge Arrival Online Matching: The Power of Free Disposal on Acyclic Graphs
Tianle Jiang, Yuhao Zhang
Online matching is a fundamental problem in the study of online algorithms. We study the problem under a very general arrival model: the edge arrival model. Free disposal is an imp…