Nicole Wein

activity

20182026

most citedBeyond 2-approximation for k-Center in Graphs

3 citations · 5 across the 10 of their papers we have counts for

collaborators

Showing 2024Show all

2 papers · 1 filter

cs.DS2024

Detecting Disjoint Shortest Paths in Linear Time and More

Shyan Akmal, Virginia Vassilevska Williams, Nicole Wein

In the $k$ -Disjoint Shortest Paths ( $k$ -DSP) problem, we are given a weighted graph $G$ on $n$ nodes and $m$ edges with specified source vertices $s_{1}, \dots, s_{k}$ , and target vert…

cs.DS2024

Additive Spanner Lower Bounds with Optimal Inner Graph Structure

Greg Bodwin, Gary Hoppenworth, Virginia Vassilevska Williams +2

We construct $n$ -node graphs on which any $O (n)$ -size spanner has additive error at least $+ Ω (n^{3/17})$ , improving on the previous best lower bound of $Ω (n^{1/7})$ [Bodwin-Hoppenw…