3 citations · 5 across the 10 of their papers we have counts for
24 papers · 1 filter
Exponential Lower Bounds for Integer-Weighted Shortest-Paths Preservers of DAGs
Michael Yi Wang, Nicole Wein
We study a graph simplification problem introduced by Bernstein, Bodwin, and Wein [ITCS'24]. We start with a graph with arbitrarily large positive edge weights and the goal is to r…
DAG Covers for Structured Graphs: The Steiner Point Effect
Sujoy Bhore, Hsien-Chih Chang, Jonathan Conroy +4
Given a weighted digraph , a -DAG cover is a collection of dominating DAGs such that all distances are approximately preserved: for every pair $(u,v…
Beyond 2-approximation for k-Center in Graphs
Ce Jin, Yael Kirkpatrick, Virginia Vassilevska Williams +1
We consider the classical -Center problem in undirected graphs. The problem is known to have a polynomial-time 2-approximation. There are even -approximations r…
Detecting Disjoint Shortest Paths in Linear Time and More
Shyan Akmal, Virginia Vassilevska Williams, Nicole Wein
In the -Disjoint Shortest Paths (-DSP) problem, we are given a weighted graph on nodes and edges with specified source vertices , and target vert…
Additive Spanner Lower Bounds with Optimal Inner Graph Structure
Greg Bodwin, Gary Hoppenworth, Virginia Vassilevska Williams +2
We construct -node graphs on which any -size spanner has additive error at least , improving on the previous best lower bound of [Bodwin-Hoppenw…
Are there graphs whose shortest path structure requires large edge weights?
Aaron Bernstein, Greg Bodwin, Nicole Wein
The aspect ratio of a (positively) weighted graph is the ratio of its maximum edge weight to its minimum edge weight. Aspect ratio commonly arises as a complexity measure in gr…
A Local-to-Global Theorem for Congested Shortest Paths
Shyan Akmal, Nicole Wein
Amiri and Wargalla (2020) proved the following local-to-global theorem in directed acyclic graphs (DAGs): if is a weighted DAG such that for each subset of 3 nodes there is…
Closing the Gap Between Directed Hopsets and Shortcut Sets
Aaron Bernstein, Nicole Wein
For an n-vertex directed graph , a -\emph{shortcut set} is a set of additional edges such that has the same transitive closure…
Approximation Algorithms and Hardness for -Pairs Shortest Paths and All-Nodes Shortest Cycles
Mina Dalirrooyfard, Ce Jin, Virginia Vassilevska Williams +1
We study the approximability of two related problems on graphs with nodes and edges: -Pairs Shortest Paths (-PSP), where the goal is to find a shortest path between $…
Online List Labeling: Breaking the Barrier
Michael A. Bender, Alex Conway, Martín Farach-Colton +3
The online list labeling problem is an algorithmic primitive with a large literature of upper bounds, lower bounds, and applications. The goal is to store a dynamically-changing se…
Better Lower Bounds for Shortcut Sets and Additive Spanners via an Improved Alternation Product
Kevin Lu, Virginia Vassilevska Williams, Nicole Wein +1
We obtain improved lower bounds for additive spanners, additive emulators, and diameter-reducing shortcut sets. Spanners and emulators are sparse graphs that approximately preserve…
Hardness of Token Swapping on Trees
Oswin Aichholzer, Erik D. Demaine, Matias Korman +6
Given a graph where every vertex has exactly one labeled token, how can we most quickly execute a given permutation on the tokens? In (sequential) token swapping, the goal is to us…
Algorithms for the Minimum Dominating Set Problem in Bounded Arboricity Graphs: Simpler, Faster, and Combinatorial
Adir Morgan, Shay Solomon, Nicole Wein
We revisit the minimum dominating set problem on graphs with arboricity bounded by . Bansal and Umboh [BU17] gave an -approximation LP rounding algorithm, which also trans…
Tight Conditional Lower Bounds for Approximating Diameter in Directed Graphs
Mina Dalirrooyfard, Nicole Wein
Among the most fundamental graph parameters is the Diameter, the largest distance between any pair of vertices. Computing the Diameter of a graph with edges requires $m^{2-o(1)…
New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners
Thiago Bergamaschi, Monika Henzinger, Maximilian Probst Gutenberg +2
Maintaining and updating shortest paths information in a graph is a fundamental problem with many applications. As computations on dense graphs can be prohibitively expensive, and…
Memoryless Worker-Task Assignment with Polylogarithmic Switching Cost
Aaron Berger, William Kuszmaul, Adam Polak +2
We study the basic problem of assigning memoryless workers to tasks with dynamically changing demands. Given a set of workers and a multiset of tasks,…
Lower Bounds for Dynamic Distributed Task Allocation
Hsin-Hao Su, Nicole Wein
We study the problem of distributed task allocation in multi-agent systems. Suppose there is a collection of agents, a collection of tasks, and a demand vector, which specifies the…
New Algorithms and Hardness for Incremental Single-Source Shortest Paths in Directed Graphs
Maximilian Probst Gutenberg, Virginia Vassilevska Williams, Nicole Wein
In the dynamic Single-Source Shortest Paths (SSSP) problem, we are given a graph subject to edge insertions and deletions and a source vertex , and the goal is to…
Tight Approximation Algorithms for Bichromatic Graph Diameter and Related Problems
Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas +1
Some of the most fundamental and well-studied graph parameters are the Diameter (the largest shortest paths distance) and Radius (the smallest distance for which a "center" node ca…
Improved Dynamic Graph Coloring
Shay Solomon, Nicole Wein
This paper studies the fundamental problem of graph coloring in fully dynamic graphs. Since the problem of computing an optimal coloring, or even approximating it to within $n^{1-ε…
Approximation Algorithms for Min-Distance Problems
Mina Dalirrooyfard, Virginia Vassilevska Williams, Nikhil Vyas +3
We study fundamental graph parameters such as the Diameter and Radius in directed graphs, when distances are measured using a somewhat unorthodox but natural measure: the distance…
Algorithms and Hardness for Diameter in Dynamic Graphs
Bertie Ancona, Monika Henzinger, Liam Roditty +2
The diameter, radius and eccentricities are natural graph parameters. While these problems have been studied extensively, there are no known dynamic algorithms for them beyond the…
Fully Dynamic MIS in Uniformly Sparse Graphs
Krzysztof Onak, Baruch Schieber, Shay Solomon +1
We consider the problem of maintaining a maximal independent set (MIS) in a dynamic graph subject to edge insertions and deletions. Recently, Assadi, Onak, Schieber and Solomon (ST…
Towards Tight Approximation Bounds for Graph Diameter and Eccentricities
Arturs Backurs, Liam Roditty, Gilad Segal +2
Among the most important graph parameters is the Diameter, the largest distance between any two vertices. There are no known very efficient algorithms for computing the Diameter ex…