\documentclass{article}
\usepackage[T1]{fontenc}
\usepackage[latin9]{inputenc}
\usepackage{array}
\usepackage{rotating}
\usepackage[italian]{babel}
\usepackage{amsmath}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Steiner trees}

Gli alberi di Steiner nel piano Euclideo hanno interessanti proprietà.
Il problema con 3 punti è il famoso prolema di Fermat-Torricelli, con il caso particolare studiato da Heinen nel 1837
Nel problema con 4 punti, lo Steiner tree è meglio della 1-mediana: $1+sqrt{3}$.
Con $n$ punti, il numero di Steiner points è sempre $\leq n-2$.
Ogni Steiner point ha grado 3 e angoli di 120 gradi.
La parte non-lineare quindi è facile, mentre le parte combinatoria è difficile: il numero di topologie è fattoriale in $n$.
Per $n=20$, $p=3$ dimensioni, ci vogliono più di 30 giorni di calcolo.\\

Idea di lavoro: fare un branch-and-bound e un'euristica.
Ci si può basare peresempio sulla triangolazione di Delaunay: triple di punti vicini (triangoli di Delaunay) sono collegate da punti di Steiner.\\

Riferimenti:
\begin{itemize}
\item Maculan, Michela, Xavier (2000)
\item Fampa, Maculan (2004), formulazione con "Big M"
\item Maculan, Ouzia, Pinto (2020)
\item Xue, Ye, SIAM J. on Opt. 4 (97)
\end{itemize}

Dati di input: Dreyer, Overton, J. of Global Opt. (98) + Maculan, ITOR 23 (2016)\\

V. anche: Smith, Algoritmica 7 (1992).\\

Adatto per tesi di laurea (euristica) e per progetto d'esame di Complementi di R.O. o tesi magistrale (algoritmo esatto).

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{document}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
