6 papers · 1 filter
Improved Upper Bounds for the Directed Flow-Cut Gap
Greg Bodwin, Luba Samborska
We prove that the flow-cut gap for -node directed graphs is at most . This is the first improvement since a previous upper bound of by…
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 Unified View of Graph Regularity via Matrix Decompositions
Greg Bodwin, Santosh Vempala
We prove algorithmic weak and \Szemeredi{} regularity lemmas for several classes of sparse graphs in the literature, for which only weak regularity lemmas were previously known. Th…
An Alternate Proof of Near-Optimal Light Spanners
Greg Bodwin
In 2016, a breakthrough result of Chechik and Wulff-Nilsen [SODA '16] established that every -node graph has a -spanner of lightness $O_{\varepsilon}(…
Opponent Indifference in Rating Systems: A Theoretical Case for Sonas
Greg Bodwin, Forest Zhang
In competitive games, it is common to assign each player a real number rating signifying their skill level. A rating system is a procedure by which player ratings are adjusted upwa…
Folklore Sampling is Optimal for Exact Hopsets: Confirming the Barrier
Greg Bodwin, Gary Hoppenworth
For a graph , a -diameter-reducing exact hopset is a small set of additional edges that, when added to , maintains its graph metric but guarantees that all node pairs…