Showing 2020Show all
3 papers · 1 filter
cs.DS2020
Near-linear Size Hypergraph Cut Sparsifiers
Yu Chen, Sanjeev Khanna, Ansh Nagda
Cuts in graphs are a fundamental object of study, and play a central role in the study of graph algorithms. The problem of sparsifying a graph while approximately preserving its cu…
cs.DS2020
Sublinear Algorithms and Lower Bounds for Metric TSP Cost Estimation
Yu Chen, Sampath Kannan, Sanjeev Khanna
We consider the problem of designing sublinear time algorithms for estimating the cost of a minimum metric traveling salesman (TSP) tour. Specifically, given access to a $n \times…
cs.DS2020
Near-Perfect Recovery in the One-Dimensional Latent Space Model
Yu Chen, Sampath Kannan, Sanjeev Khanna
Suppose a graph is stochastically created by uniformly sampling vertices along a line segment and connecting each pair of vertices with a probability that is a known decreasing…