6 papers · 1 filter
Tree Search With Distributional Predictions
Michael Dinitz, Bob Dong
Learning-augmented algorithms use machine-learned predictions to improve classical algorithmic guarantees when the predictions are accurate, while retaining rigorous performance gu…
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 ex…
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…
Edge-Private Matching Kernels Through Local Decoding
Michael Dinitz, George Z. Li, Quanquan C. Liu +1
A matching is a set of edges with no shared endpoints. We study how participants can retain useful matching structure when each knows its own relationships but those relationships…
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…