6 papers
Ski Rental with Distributional Predictions of Unknown Quality
Qiming Cui, Michael Dinitz
We revisit the central online problem of ski rental in the "algorithms with predictions" framework from the point of view of distributional predictions. Ski rental was one of the f…
Differentially Private Matchings
Michael Dinitz, George Z. Li, Quanquan C. Liu +1
Computing matchings in graphs is a foundational algorithmic task. Despite extensive interest in differentially private (DP) graph analysis, work on privately computing matching sol…
Learning-Augmented Online Algorithms for Nonclairvoyant Joint Replenishment Problem with Deadlines
Michael Dinitz, Jeremy T. Fineman, Seeun William Umboh
This paper considers using predictions in the context of the online Joint Replenishment Problem with Deadlines (JRP-D). Prior work includes asymptotically optimal competitive ratio…
Controlling tail risk in two-slope ski rental
Qiming Cui, Michael Dinitz
We study the optimal solution to a general two-slope ski rental problem with a tail risk, i.e., the chance of the competitive ratio exceeding a value is bounded by . This…
A Generalized Binary Tree Mechanism for Differentially Private Approximation of All-Pair Distances
Michael Dinitz, Chenglin Fan, Jingcheng Liu +2
We study the problem of approximating all-pair distances in a weighted undirected graph with differential privacy, introduced by Sealfon [Sea16]. Given a publicly known undirected…
Differentially Private Algorithms for Graph Cuts: A Shifting Mechanism Approach and More
Rishi Chandra, Michael Dinitz, Chenglin Fan +1
In this paper, we address the challenge of differential privacy in the context of graph cuts, specifically focusing on the multiway cut and the minimum -cut. We introduce edge-d…