5 papers · 1 filter
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…
Parallel Set Cover and Hypergraph Matching via Uniform Random Sampling
Laxman Dhulipala, Michael Dinitz, Jakub ÅÄ cki +1
The SetCover problem has been extensively studied in many different models of computation, including parallel and distributed settings. From an approximation point of view, there a…