3 papers
cs.DS2025
A Little Clairvoyance Is All You Need
Anupam Gupta, Haim Kaplan, Alexander Lindermayr +2
We revisit the classical problem of minimizing the total flow time of jobs on a single machine in the online setting where jobs arrive over time. It has long been known that the Sh…
cs.DS2025
Near-Optimal Differentially Private Graph Algorithms via the Multidimensional AboveThreshold Mechanism
Laxman Dhulipala, Monika Henzinger, George Z. Li +3
Many differentially private and classical non-private graph algorithms rely crucially on determining whether some property of each vertex meets a threshold. For example, for the $k…
cs.DS2025
Weighted Matching in a Poly-Streaming Model
Ahammed Ullah, S. M. Ferdous, Alex Pothen
We introduce the poly-streaming model, a generalization of streaming models of computation in which processors process data streams containing a total of items. The alg…