Showing cs.DSShow all
3 papers · 1 filter
cs.DS2026
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…
cs.DS2026
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…
cs.DS2024
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…