Some New Results on Random Points in the Unit Square

on YouTube ↗23m

" summary

Random points in the unit square get Euclidean weights but edges are kept independently with probability p, and the analysis shows that for constant p there is beta_p exists for constant p so TSP length scales like beta_p sqrt n while for p tiny geometry breaks down. Constrained Euclidean functionals differ: bounded-degree MSTs and girth-restricted 2-factors give strictly larger constants and HK bound < TSP. Gadget constructions and first-moment/patching arguments prove that simple branch-and-bound or scale-free heuristics fail and that branch-and-bound with HK lower bounds takes almost exponential time.

AI-written summary · about

" chapters (5)

1. 0:00Start
2. 6:30Euclidean Functionals.
3. 15:27Branch and Bound for TSP
4. 17:03Scale-Free Heuristics
5. 20:26Open Problems

" related talks

• 52mBeyond Big-O: Statistical Analysis of Performance ScalingHolger H. Hoos · Learning, Algorithm Design and Beyond Worst-Case Analysis
• 29mApplying Randomized Methods for Zonotope Enumeration and...David Gleich · Randomized Numerical Linear Algebra and Applications 2018
• 01h 03mA New Upper Bound for the Heilbronn Triangle ProblemCosmin Pohoata · Structural Results 2023
• 01h 07mWhere the Hard Things AreAndrea Montanari · Counting Complexity and Phase Transitions Boot Camp
• 43mOn Using Graph Distances to Estimate Euclidean and Related DistancesEry Arias-Castro · Robust and High-Dimensional Statistics (Simons Institute workshop, 2018)
• 01h 08mThe Simple, Little and Slow Things Count: On Parameterized Counting ComplexityRadu-Cristian Curticapean · Counting Complexity and Phase Transitions Boot Camp
• 50mRandom Combinatorial MatricesAmin Coja-Oghlan · Algorithmic Advances for Statistical Inference with Combinatorial Structure
• 28mRandomized Constrained Matrix DecompositionsBenjamin Erichson · Randomized Numerical Linear Algebra and Applications 2018