# Colloquium: Power and Limits in Algorithm Design

## Structures in Algorithm Design: Power and Limits

Talk by Hung Le

### Distance Sparsification in Bounded Geometry

#### Bounded Geometry

*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).

Doubling Spaces

#### Distance Sparsification

Question: Trade-off between stretch and lightness.

### Application of Spanners

- Routing
- ML
- 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.

General graph

#### Improvement

Steiner Euclidean dimension. Steiner pointer = points not in the original set. Reduces the weight, but always has more edges than MST. Reduces sparsity quadratically.

### Combinatorial Optimization

- Traveling Salesperson Problem
- Local Search

#### Bounded clique minor

Graphs that can be drawn without edge crossing

Tree-like graphs

#### Subset TSP

Shortest tour in a subset of the weighted graph (can use other points not in the target subset).

Approximation

- Christofides’ algorithm in poly time

#### Light Preservers

- Nearly optimal
- Light

Lift solution from light solution to the original graph.

#### Local Search

#### Sublinear Separation

### Future Work

- 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