Donald Bren School of Information and Computer Sciences

We find the balanced cut in a graph that minimizes the maximum difference between edge lengths, in time O(m + n^2 log n), improving a previous O(m + n^2.5) bound. We use subroutines for solving a dynamic subset sum problem, in time O(l log l log n) per operation in the fully dynamic setting, or in time O(l log n) per operation in the semi-online setting in which one can predict a superset of future deletions.