Zobrazeno 1 - 10
of 125
pro vyhledávání: '"Dinitz, Michael"'
In this paper, we address the challenge of differential privacy in the context of graph cuts, specifically focusing on the minimum $k$-cut and multiway cut problems. We introduce edge-differentially private algorithms that achieve nearly optimal perf
Externí odkaz:
http://arxiv.org/abs/2407.06911
Autor:
Dinitz, Michael1 (AUTHOR) mdinitz@cs.jhu.edu, Fineman, Jeremy2 (AUTHOR) jfineman@cs.georgetown.edu, Gilbert, Seth3 (AUTHOR) seth.gilbert@comp.nus.edu.sg, Newport, Calvin2 (AUTHOR) cn248@georgetown.edu
Publikováno v:
Journal of the ACM. Jun2024, Vol. 71 Issue 3, p1-24. 24p.
Emerging reconfigurable optical communication technologies allow to enhance datacenter topologies with demand-aware links optimized towards traffic patterns. This paper studies the algorithmic problem of jointly optimizing topology and routing in suc
Externí odkaz:
http://arxiv.org/abs/2401.04638
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 analytics, and so privacy is a natural requirement. All known private a
Externí odkaz:
http://arxiv.org/abs/2308.10316
The classical ski-rental problem admits a textbook 2-competitive deterministic algorithm, and a simple randomized algorithm that is $\frac{e}{e-1}$-competitive in expectation. The randomized algorithm, while optimal in expectation, has a large varian
Externí odkaz:
http://arxiv.org/abs/2308.05067
One of the most important and well-studied settings for network design is edge-connectivity requirements. This encompasses uniform demands such as the Minimum $k$-Edge-Connected Spanning Subgraph problem as well as nonuniform demands such as the Surv
Externí odkaz:
http://arxiv.org/abs/2304.06656
While much of network design focuses mostly on cost (number or weight of edges), node degrees have also played an important role. They have traditionally either appeared as an objective, to minimize the maximum degree (e.g., the Minimum Degree Spanni
Externí odkaz:
http://arxiv.org/abs/2302.11475
The research area of algorithms with predictions has seen recent success showing how to incorporate machine learning into algorithm design to improve performance when the predictions are correct, while retaining worst-case guarantees when they are no
Externí odkaz:
http://arxiv.org/abs/2210.12438
A $t$-emulator of a graph $G$ is a graph $H$ that approximates its pairwise shortest path distances up to multiplicative $t$ error. We study fault tolerant $t$-emulators, under the model recently introduced by Bodwin, Dinitz, and Nazari [ITCS 2022] f
Externí odkaz:
http://arxiv.org/abs/2209.03675
The best known solutions for $k$-message broadcast in dynamic networks of size $n$ require $\Omega(nk)$ rounds. In this paper, we see if these bounds can be improved by smoothed analysis. We study perhaps the most natural randomized algorithm for dis
Externí odkaz:
http://arxiv.org/abs/2208.05998