Colloquium: Power and Limits in Algorithm Design

Structures in Algorithm Design: Power and Limits

Talk by Hung Le

Similar to talk

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

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

  1. Traveling Salesperson Problem
  2. 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

Light Preservers

  • Nearly optimal
  • Light

Lift solution from light solution to the original graph.

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
Avatar
Cody Perakslis
Student

My interests are in data science, distributed computing, and philosophy.