# PP Final
## Steiner Trees
* **NP-Hard** problem -> use approximation
* Often used in VLSI routing problem
* Terminal point -> **must be included** in solution
* non-terminal point can be added to reduce cost
* cost of a Steiner Tree is the sum of all edge weights
* goal is to **minimize the cost**

## Algorithms
<!-- [LP-base](https://dl.acm.org/doi/10.1145/1806689.1806769): approximation factor 1.55 -->
[Robins,Zelikovsky](https://www.cs.virginia.edu/~robins/papers/Robins_Graph_Steiner_Approximation.pdf): The tight bound of the approximation factor for Steiner Trees in a general graph is **1.55**.
[Mehlhorn](https://people.mpi-inf.mpg.de/~mehlhorn/ftp/SteinerTrees.pdf)The approximation factor is **2(1-1/l)**, where l is # of leaves in optimal tree, and the worst complexity is $O(|E|+|V|log|V|)$ -> **why don't use this?**
[KMB](http://aturing.umcs.maine.edu/~markov/SteinerTrees.pdf) The approximation factor is **2(1-1/l)**, where l is # of leaves in optimal tree, and the worst complexity is $O(S|V|^2)$

## Parallel Related Paper
[Accerlating the KMB](https://mrprajesh.co.in/pdfs/steiner-ijpp22-preprint.pdf)
* [ppt](https://mrprajesh.co.in/pdfs/sem2-v4.pdf)
<!-- * [github](https://github.com/HeathcliffAC/SteinerTreeProblem) -->

[intro of parallel STs](https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=4682068)
* Although other techniques have a better approximation ratio, the **performance bound lies in KMB** since it will be used as the first approximation in their algorithm.

[prims](https://www.reed.edu/biology/courses/bio331/files/projects/fall2016/lopez.pdf)

## TODOs
* sequential KMB
* parallel KMB (cpu/gpu)