3 citations · 5 across the 13 of their papers we have counts for
22 papers
Correlation Clustering with Random Partial Information
Rajath Rao K. N., Jens Schlöter, Sami Davies +2
Correlation clustering is a fundamental unsupervised learning problem. On complete graphs, both the min-disagreement and min-max objectives admit constant-factor approximations, ye…
Reachability with Subquadratic Cut Queries on Directed Graphs
Ben Bals, Matei Tinca, Yasamin Nazari
In the cut-query model, we have access to a (directed) graph via an oracle and we can query the size of the (directed) cut of a given subset of the vertices. One of the most elemen…
Faster Randomized and Deterministic k-Clustering on Graphs
Sebastian Forster, Yasamin Nazari, Rajath Rao K. N. +1
In this paper, we study the -clustering and -center problems on graphs, where -clustering generalizes the -median () and -means () problems. We obt…
Revisiting Diameter in Directed Graphs
Ben Bals, Joakim Blikstad, Daniel Dadush +2
The reachability diameter () of a directed graph is the maximum distance over all pairs where is reachable from . This notion is present in the def…
Greedy Algorithms for Shortcut Sets and Hopsets
Ben Bals, Joakim Blikstad, Greg Bodwin +3
For many popular graph metric sparsifiers, such as spanners, emulators, and preservers, simple and elegant greedy algorithms are known that achieve state-of-the-art or existentiall…
Approximation Algorithms for Optimal Hopsets
Michael Dinitz, Ama Koranteng, Yasamin Nazari
For a given graph , a "hopset" with hopbound and stretch is a set of edges such that between every pair of vertices and , there is a path with at most hop…
Dynamic algorithms for k-center on graphs
Emilio Cruciani, Sebastian Forster, Gramoz Goranci +2
In this paper we give the first efficient algorithms for the -center problem on dynamic graphs undergoing edge updates. In this problem, the goal is to partition the input into…
On Dynamic Graph Algorithms with Predictions
Jan van den Brand, Sebastian Forster, Yasamin Nazari +1
We study dynamic algorithms in the model of algorithms with predictions. We assume the algorithm is given imperfect predictions regarding future updates, and we ask how such predic…
Fast 2-Approximate All-Pairs Shortest Paths
Michal Dory, Sebastian Forster, Yael Kirkpatrick +3
In this paper, we revisit the classic approximate All-Pairs Shortest Paths (APSP) problem in undirected graphs. For unweighted graphs, we provide an algorithm for -approximate A…
Bootstrapping Dynamic Distance Oracles
Sebastian Forster, Gramoz Goranci, Yasamin Nazari +1
Designing approximate all-pairs distance oracles in the fully dynamic setting is one of the central problems in dynamic graph algorithms. Despite extensive research on this topic,…
Deterministic Incremental APSP with Polylogarithmic Update Time and Stretch
Sebastian Forster, Yasamin Nazari, Maximilian Probst Gutenberg
We provide the first deterministic data structure that given a weighted undirected graph undergoing edge insertions, processes each update with polylogarithmic amortized update tim…
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 edges and nodes unde…
Epic Fail: Emulators can tolerate polynomially many edge faults for free
Greg Bodwin, Michael Dinitz, Yasamin Nazari
A -emulator of a graph is a graph that approximates its pairwise shortest path distances up to multiplicative error. We study fault tolerant -emulators, under the…
Fast Deterministic Fully Dynamic Distance Approximation
Jan van den Brand, Sebastian Forster, Yasamin Nazari
In this paper, we develop deterministic fully dynamic algorithms for computing approximate distances in a graph with worst-case update time guarantees. In particular, we obtain imp…
Vertex Fault-Tolerant Emulators
Greg Bodwin, Michael Dinitz, Yasamin Nazari
A -spanner of a graph is a sparse subgraph that preserves its shortest path distances up to a multiplicative stretch factor of , and a -emulator is similar but not req…
Online Allocation and Display Ads Optimization with Surplus Supply
Melika Abolhassani, Hossein Esfandiari, Yasamin Nazari +3
In this work, we study a scenario where a publisher seeks to maximize its total revenue across two sales channels: guaranteed contracts that promise to deliver a certain number of…
Near-Optimal Decremental Hopsets with Applications
Jakub Łącki, Yasamin Nazari
Given a weighted undirected graph , a hopset of hopbound and stretch is a set of edges such that for any pair of nodes , there is a path in $…
Massively Parallel Algorithms for Distance Approximation and Spanners
Amartya Shankha Biswas, Michal Dory, Mohsen Ghaffari +2
Over the past decade, there has been increasing interest in distributed/parallel algorithms for processing large-scale graphs. By now, we have quite fast algorithms -- usually subl…
Sparse Hopsets in Congested Clique
Yasamin Nazari
We give the first Congested Clique algorithm that computes a sparse hopset with polylogarithmic hopbound in polylogarithmic time. Given a graph , a -hopset with…
Lasserre Integrality Gaps for Graph Spanners and Related Problems
Michael Dinitz, Yasamin Nazari, Zeyu Zhang
There has been significant recent progress on algorithms for approximating graph spanners, i.e., algorithms which approximate the best spanner for a given input graph. Essentially…
Massively Parallel Approximate Distance Sketches
Michael Dinitz, Yasamin Nazari
Data structures that allow efficient distance estimation (distance oracles, distance sketches, etc.) have been extensively studied, and are particularly well studied in centralized…
Distributed Distance-Bounded Network Design Through Distributed Convex Programming
Michael Dinitz, Yasamin Nazari
Solving linear programs is often a challenging task in distributed settings. While there are good algorithms for solving packing and covering linear programs in a distributed manne…