5 papers · 1 filter
Simpler Algorithms for Knapsack, Subset Sum, and Min-Plus Convolution
Trevor Vaughn
We simplify algorithms for Knapsack, output-sensitive Subset Sum, and near-convex min-plus convolution. For bounded Knapsack, we give a deterministic algorithm using $O(N+W^2\log^3…
Faster Minimum k-Cut II: Improved Randomized and Deterministic Algorithms for Weighted Graphs
Trevor Vaughn
The Minimum -Cut problem asks for a minimum-weight set of edges whose removal leaves an undirected weighted graph with at least connected components. We consider only $k\ge3…
Faster Minimum k-Cut I: Simple and Sparse Weighted Graphs
Jason Li, Trevor Vaughn
The minimum -cut problem asks for the fewest edges whose removal leaves an input graph with at least connected components. Previously, the best algorithm for simple graphs r…
A Simple Las Vegas Algorithm for Sparse Nonnegative Convolution
Trevor Vaughn
Let be nonnegative vectors and let . We give a Las Vegas algorithm that computes in …
Deterministic Spectral Sparsification in Almost-Linear Time for Dense Graphs
Jason Li, Trevor Vaughn
A spectral sparsifier of a weighted graph is a reweighted subgraph whose Laplacian quadratic form approximates that of the original graph. Let be a positively weighted -vert…