Notas Hellout

- DP algo - metric-TSP and euclidean-TSP approx

Linear time **measure** approximation of a **set union** given oracles for **uniform sampling on the multiset union** and **membership testing on the insertion-order labeled set union**. **measure**: `|S|` e.g. volume,...

See "A Separator Theorem for Planar Graphs" by Lipton and Tarjan.

Least-squares approximation

1

min_b Ab - y b = A^+ y where A^+ is the [pseudoinverse](https://en.wikipedia.org/wiki/Moore%E2%80%93Penrose_inverse) of A See *Introduction to algorithms* by *TH Cormen, CE Leiserson, RL Rivest, C Stein*.

## Reference @article{thomassen1994every, title={Every planar graph is 5-choosable}, author={Thomassen, Carsten}, journal={Journal of Combinatorial Theory Series B}, volume={62}, number={1}, pages={180--181}, year={1994}, publisher={Academic Press, Inc. Orlando, FL, USA} } ## Algorithm Input:...

See [*Small-dimensional linear programming and convex hulls made easy*](https://link.springer.com/article/10.1007/BF02574699) by *Raimund Seidel*.

https://en.wikipedia.org/wiki/Principal_component_analysis

https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm

See https://blog.burntsushi.net/ripgrep/#literal-optimizations.