Jack Spalding-Jamieson

Vladimir Kolmogorov, Jack Spalding-Jamieson

We present a family of fast pseudo-approximation algorithms for the minimum balanced vertex separator problem in a graph. Given a graph $G=(V,E)$ with $n$ vertices and $m$ edges, and a (constant) balance parameter $c\in(0,1/2)$, where $G$ has some (unknown) $c$-balanced vertex separator of size ${\rm OPT}_c$, we give a (Monte-Carlo randomized) algorithm running in $O(n^{O(\varepsilon)}m^{1+o(1)})$ time that produces a $Θ(1)$-balanced vertex separator of size $O({\rm OPT}_c\cdot\sqrt{(\log n)/\varepsilon})$ for any value $\varepsilon\in[Θ(1/\log(n)),Θ(1)]$. In particular, for any function $f(n)=ω(1)$ (including $f(n)=\log\log n$, for instance), we can produce a vertex separator of size $O({\rm OPT}_c\cdot\sqrt{\log n}\cdot f(n))$ in time $O(m^{1+o(1)})$. Moreover, for an arbitrarily small constant $\varepsilon=Θ(1)$, our algorithm also achieves the best-known approximation ratio for this problem in $O(m^{1+Θ(\varepsilon)})$ time. The algorithms are based on a semidefinite programming (SDP) relaxation of the problem, which we solve using the Matrix Multiplicative Weight Update (MMWU) framework of Arora and Kale. Our oracle for MMWU uses $O(n^{O(\varepsilon)}\text{polylog}(n))$ almost-linear time maximum-flow computations, and would be sped up if the time complexity of maximum-flow improves.

Jack Spalding-Jamieson, Eliot Wong Robson, Da Wei Zheng

For very large values of $k$, we consider methods for fast $k$-means clustering of massive datasets with $10^7\sim10^9$ points in high-dimensions ($d\geq100$). All current practical methods for this problem have runtimes at least $Ω(k^2)$. We find that initialization routines are not a bottleneck for this case. Instead, it is critical to improve the speed of Lloyd's local-search algorithm, particularly the step that reassigns points to their closest center. Attempting to improve this step naturally leads us to leverage approximate nearest-neighbor search methods, although this alone is not enough to be practical. Instead, we propose a family of problems we call "Seeded Approximate Nearest-Neighbor Search", for which we propose "Seeded Search-Graph" methods as a solution.

Ivor van der Hoog, Eva Rotenberg, Jack Spalding-Jamieson et al.

Many fundamental problems in computational geometry admit no algorithm running in $o(n \log n)$ time for $n$ planar input points, via classical reductions from sorting. Prominent examples include the computation of convex hulls, quadtrees, onion layer decompositions, Euclidean minimum spanning trees, KD-trees, Voronoi diagrams, and decremental closest-pair. A classical result shows that, given $n$ points sorted along a single direction, the convex hull can be constructed in linear time. Subsequent works established that for all of the other above problems, this information does not suffice. In 1989, Aggarwal, Guibas, Saxe, and Shor asked: Under which conditions can a Voronoi diagram be computed in $o(n \log n)$ time? Since then, the question of whether sorting along TWO directions enables a $o(n \log n)$-time algorithm for such problems has remained open and has been repeatedly mentioned in the literature. In this paper, we introduce the Presort Hierarchy: A problem is 1-Presortable if, given a sorting along one axis, it permits a (possibly randomised) $o(n \log n)$-time algorithm. It is 2-Presortable if sortings along both axes suffice. It is Presort-Hard otherwise. Our main result is that quadtrees, and by extension Delaunay triangulations, Voronoi diagrams, and Euclidean minimum spanning trees, are 2-Presortable: we present an algorithm with expected running time $O(n \sqrt{\log n})$. This addresses the longstanding open problem posed by Aggarwal, Guibas, Saxe, and Shor (albeit randomised). We complement this result by showing that some of the other above geometric problems are also 2-Presortable or Presort-Hard.

Paul Liu, Jack Spalding-Jamieson, Brandon Zhang et al.

This paper examines the approach taken by team gitastrophe in the CG:SHOP 2021 challenge. The challenge was to find a sequence of simultaneous moves of square robots between two given configurations that minimized either total distance travelled or makespan (total time). Our winning approach has two main components: an initialization phase that finds a good initial solution, and a $k$-opt local search phase which optimizes this solution. This led to a first place finish in the distance category and a third place finish in the makespan category.