Colloquium: Power and Limits in Algorithm Design
Structures in Algorithm Design: Power and Limits
Talk by Hung Le
Distance Sparsification in Bounded Geometry
Doubling space for peer-to-peer networks.
Finite metric space. identificiation, symmetry, triangle inequality.
Doubling dimension. Think of metric space as edge-weighted graph (by distance).
Question: Trade-off between stretch and lightness.
Application of Spanners
- Distributed Systems
Construct Minimum Spanning Tree
Kruskal algorithm Add t stretch factor for the determination of adding edge. Simple adjustment to algorithm.
Question: What is the sparsity of the algorithm.
Steiner Euclidean dimension. Steiner pointer = points not in the original set. Reduces the weight, but always has more edges than MST. Reduces sparsity quadratically.
- Traveling Salesperson Problem
- Local Search
Bounded clique minor
Graphs that can be drawn without edge crossing
Shortest tour in a subset of the weighted graph (can use other points not in the target subset).
- Christofides’ algorithm in poly time
- Nearly optimal
Lift solution from light solution to the original graph.
- Simple/Practical Algorithms, specifically sublinear separation
- Does local search work for all local problems?
Ex: Fails for weighted problem
- Embed into tree-like graphs
- The key is to closed under submatrices