5 papers · 1 filter
Subquadratic Approximation Algorithms for Separating Two Points with Objects in the Plane
Jayson Lynch, Jack Spalding-Jamieson
The (unweighted) point-separation problem asks, given a pair of points and in the plane, and a set of candidate geometric objects, for the minimum-size subset of objects wh…
Reweighted Spectral Partitioning Works: A Simple Algorithm for Vertex Separators in Special Graph Classes
Jack Spalding-Jamieson
We establish that a practical polynomial-time algorithm obtains near-optimal -balanced vertex separators for a number of graph classes, including genus- graphs, -m…
Separating Two Points with Obstacles in the Plane: Improved Upper and Lower Bounds
Jack Spalding-Jamieson, Anurag Murty Naredla
Given two points in the plane, and a set of "obstacles" given as curves through the plane with assigned weights, we consider the point-separation problem, which asks for the minimu…
Slant/Gokigen Naname is NP-complete, and Some Variations are in P
Jayson Lynch, Jack Spalding-Jamieson
In this paper we show that a generalized version of the Nikoli puzzle Slant is NP-complete. We also give polynomial time algorithms for versions of the puzzle where some constraint…
Scalable k-Means Clustering for Large k via Seeded Approximate Nearest-Neighbor Search
Jack Spalding-Jamieson, Eliot Wong Robson, Da Wei Zheng
For very large values of , we consider methods for fast -means clustering of massive datasets with points in high-dimensions (). All current practica…