29 citations · 45 across the 12 of their papers we have counts for
Showing 2023Show all
3 papers · 1 filter
cs.DS2023
Controlling Tail Risk in Online Ski-Rental
Michael Dinitz, Sungjin Im, Thomas Lavastida +2
The classical ski-rental problem admits a textbook 2-competitive deterministic algorithm, and a simple randomized algorithm that is -competitive in expectation. The…
cs.DS2023
Almost Tight Bounds for Differentially Private Densest Subgraph
Michael Dinitz, Satyen Kale, Silvio Lattanzi +1
We study the Densest Subgraph (DSG) problem under the additional constraint of differential privacy. DSG is a fundamental theoretical question which plays a central role in graph a…
cs.DS2023
Improved Approximations for Relative Survivable Network Design
Michael Dinitz, Ama Koranteng, Guy Kortsarz +1
One of the most important and well-studied settings for network design is edge-connectivity requirements. This encompasses uniform demands such as the Minimum -Edge-Connected Sp…