Michal Dory

activity

20172026

most citedHardness of Distributed Optimization

2 citations · 4 across the 12 of their papers we have counts for

collaborators

Showing 2022Show all

3 papers · 1 filter

cs.DS2022

A Nearly Time-Optimal Distributed Approximation of Minimum Cost $k$ -Edge-Connected Spanning Subgraph

Michal Dory, Mohsen Ghaffari

The minimum-cost $k$ -edge-connected spanning subgraph ( $k$ -ECSS) problem is a generalization and strengthening of the well-studied minimum-cost spanning tree (MST) problem. While t…

cs.DS2022

New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths

Michal Dory, Sebastian Forster, Yasamin Nazari +1

We provide new tradeoffs between approximation and running time for the decremental all-pairs shortest paths (APSP) problem. For undirected graphs with $m$ edges and $n$ nodes unde…

cs.DS2022

Near-Optimal Distributed Dominating Set in Bounded Arboricity Graphs

Michal Dory, Mohsen Ghaffari, Saeed Ilchi

We describe a simple deterministic $O (ε^{- 1} lo g Δ)$ round distributed algorithm for $(2 α + 1) (1 + ε)$ approximation of minimum weighted dominating set on graph…

A Nearly Time-Optimal Distributed Approximation of Minimum Cost k-Edge-Connected Spanning Subgraph

New Tradeoffs for Decremental Approximate All-Pairs Shortest Paths

Near-Optimal Distributed Dominating Set in Bounded Arboricity Graphs

A Nearly Time-Optimal Distributed Approximation of Minimum Cost $k$ -Edge-Connected Spanning Subgraph